LeetCode之最长回文子串超详细java讲解

 

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

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

输入：s = "cbbd"
输出："bb"

思路一:暴力枚举，将每一种情况都列出来，然后判断是否为回文串，最后选出最长的
回文子串。
时间复杂度：O(n^3)
空间复杂度：O(1)

完整代码如下：

 public String longestPalindrome(String s){
        int len = s.length();
        if(len<2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        for(int i = 0;i<len-1;i++){
            for(int j = i+1;j<len;j++){
                 if(j-i+1>maxLen && validP(charArray,i,j )){
                     maxLen = j - i +1;
                     begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
    public boolean validP(char[] chars,int i,int j){
        while (i<j){
            if(chars[i] != chars[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }