给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思路：

首先想到暴力匹配，两个循环，搜索出所有长度大于等于2的子串，然后进行回文判断，使用一个最大的长度变量，和起始位置。

class Solution {
    //暴力匹配
    public String longestPalindrome(String s) {
            int n=s.length();
            int maxlen=1;
            int begin=0;
       //这里抖个小机灵，如果使用s.charAt(i),底层函数会每次都要进行边界判断。速度慢
            char []chars=s.toCharArray();
            if(n<2){
                return s;
            }
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    if(maxlen<j-i+1&&validPalindromic(chars,i,j)){
                        maxlen=j-i+1;
                        begin=i;
                    }
                }
            }
            return s.substring(begin,begin+maxlen);
    }

    private boolean validPalindromic(char[] chars, int i, int j) {
        while(i<j){
            if(chars[i]!=chars[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

时间复杂度巨高！O(N3)，两层for循环，里面还套着一个回文检测函数。

思路二：

5.最长回文子串

全站热榜