LeetCode题解：最长回文子串

题目描述

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

示例

输入：s="abcbad"
输出："abcba"

方法思路

暴力破解法

class Solution {
    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&&validPalindromic(charArray,i,j)){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,maxLen+begin);
    }

/**
判断是否是回文串
 */
    private boolean validPalindromic(char[] charArray,int left,int right){
        while(left<right){
            if(charArray[left]!=charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n^3)，n为字符串长度。
• 空间复杂度：O(1)，只用到常数个临时变量。

动态规划法

对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的字母取出之后，它仍然是个回文串。例如，对于字符串“abcba”，取出首尾之后“bcb”仍然是个回文串。
根据这样的规律，我们的思路就可以向动态规划方向发展。

• 状态：dp[]i[j]表示子串s[i..j]是否为回文子串
• 得到状态转移方程：dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]
  边界条件:j - 1 - (i + 1) + 1 < 2，整理的j - i < 3（即只有一个元素的时候）
• 初始化:dp[i][j] = true
• 输出：在得到一个状态的值为true的时候，记录起始位置和长度，填表完成以后再截取
  下面以“babab”为例探索填表的过程
  image.png

由于dp[i][j]参考它左下方的值：所以应该先升序填列，再升序填行。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len<2){
            return s;
        } 
        int maxLen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[len][len];
        //其实不用初始化，下方在实现填表的时候i=j部分就全部填充为true
        for(int i = 0;i<len;i++){
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        for(int j=1;j<len;j++){
            for(int i=0;i<j;i++){
                if(charArray[i]!=charArray[j]){
                    dp[i][j] = false;
                }else{
                    if(j-i<3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,maxLen+begin);
    }
}

复杂度分析

• 时间复杂度：O(n^2)，其中n是字符串你的长度。动态规划的撞他总数为 O(n^2)，对于每个状态，我们需要转移的时间为O(1)。
• 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。