LeetCode百题【最长回文子串】

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	`输入：s = "cbbd" 输出："bb"`

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法

暴力
遍历个子串并且判断是否为回文串并记录下长度

class Solution {
    public String longestPalindrome(String s) {
       int n=s.length();
       if(n<2){
           return s;
       }
       char[] chars = s.toCharArray();
       int maxLen=1;
       int begin=0;
       for (int i = 0; i <n-1; i++) {
           for (int j = i+1;j<n; j++) {
              if(j-i+1>maxLen&&isPalindromeStr(chars,i,j)){
                  maxLen=j-i+1;
                  begin=i;
              }
           }
       }
       return s.substring(begin, begin+maxLen);
     
    }

    public static boolean isPalindromeStr(char[] chars ,int left,int right){
        while (left<right){
            if (chars[left]==chars[right]){
                left++;
                right--;
            }
            else {
                return false;
            }
        }
        return true;
    }
}

时间复杂度：O(n^3)
中心扩展法
- 枚举回文中心向外扩展

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        //特殊情况
        char[] chars = s.toCharArray();
        int maxLen = 1;//记录最长回文串的长度
        int begin = 0;//该回文串的起始下标
		//因为考虑到偶数+1的情况所以是n-1防止越界
        for (int i = 0; i < n - 1; i++) {
            //1.回文中心有两种，奇数和偶数
            int oddLen = centerExtension(chars, i, i);
            int evenLen = centerExtension(chars, i, i + 1);
            //找两者最大的那个长度
            int curMaxLen = Math.max(oddLen, evenLen);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                //记录回文串的起始位置
                begin = i - (maxLen - 1) / 2;

            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public int centerExtension(char[] chars, int left, int right) {
        //中心扩展判断 左向左 右向右
        //dabac
        //01234
        while (left >= 0 && right < chars.length) {
            if (chars[left] == chars[right]) {
                left--;
                right++;
            } else {
                break;
            }
        }
        //r-l+1为[left,right]的长度，
        //但lr都变化后才能判断的出不是回文串 此时左右指针的距离是回文串长度+2
        return right - left + 1 - 2;
    }
}