LeetCode学习笔记——最长回文子串

2020-05-21

最长回文字串，首先要明白子串和子序列的区别，子串是连续的，子序列不一定是连续的，而回文就是从左到右读，或者从右到左读都是一样的。

题目的要求是在一个字符串中找出最长的那个回文子串，比如：

s = “babad”

最长回文子串就是 “bab”， “aba” 也是一个有效答案。

而这道题我们应该怎么分析呢？

我们分析回文子串，发现它其实是关于中心对称的，

那我们就可以这样想了，是不是可以确定一个字符，将其作为中心，然后向两边延展，

如果该字符的左右两边字符相同，那就继续延展，如果不同，就记录下此时长度。

比如像这样，当以a为中心时，对比其左右两端，发现其相等，那就继续延展，而左边已经到达字符串头部，不能再继续延展，此时就要记录现在的长度。

这就是中心扩散算法，

但很快我们就会发现问题，如果仅凭判断某个字符左右两端的字符是否相等来决定扩展，你会发现下面这种情况会被抛弃，

而我们可以看的出来，该字符串的最长回文子串应该是 “babbab”，

没错，我们刚刚把中心看成是一个字符，却忽略了中心是可以为多个相同字符的，

所以我们要对将这种特殊性考虑进去，把这个看成第二种情况，

需要在延展判断之前先确定中心的字符，

这样子，当我们确定了中心字符后，就可以往两边扩展，

当不能继续扩展的时候就将当前的长度与以记录的最长回文子串长度进行比较，

更新最长的长度，并记录此时子串的起始位置

因为最后我们的结果是返回一个字符串，当我们知道子串的起始位置和长度之后，就可以使用 substring(index, index + len) 截取子串

中心扩散的代码就可以写出来了：

public String longestPalindrome(String s) {
    //特判特殊情况
    if (s == null || s.length() == 0) {
        return "";
    }
    //左右两端的指针
    int left = 0;
    int right = 0;
    //最长子串的起始位置
    int maxStart = 0;
    //最长子串的长度
    int maxLen = 0;
    //当前子串的长度，至少为一个字符
    int len = 1;
    for(int i = 0; i < s.length(); i++) {
        //i为当前位置，left，right指向左右两端
        left = i - 1;
        right = i + 1;
        //进行上述的第二种情况进行判断，找出中心的字符，如果左边相等就往左边去找，反之同理，当指针变动，此时的长度也要增加
        while(left >= 0 && s.charAt(left) == s.charAt(i)) {
            len++;
            left--;
        }
        while(right < s.length() && s.charAt(right) == s.charAt(i)) {
            len++;
            right++;
        }

//当确定了中间的子串后，开始判断两端，进行延展，每延展一次，长度加2
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            len += 2;
            left--;
        }
        //将当前的子串长度与已记录的最长长度进行比较
        if(len > maxLen) {
            maxLen = len;
            maxStart = left;
        }
        //初始化当前的子串长度
        len = 1;
    }
    //截取子串，返回，因为maxStart是等于left的，而left总是比实际的子串开始位置下标少1
    return s.substring(maxStart + 1, maxStart + maxLen + 1);
 }

中心扩散方法其实还有一种写法，

上面我们讨论了中心字符的两种情况，第一种是中心是单独的一个字符，第二种是中心有多个相等的字符，

如果将第二种情况分为中心有奇数个相等的字符和偶数个相等的字符。

现在我们就对这种情况进行讨论，但有奇数个时候，如果为 1，我们就取这个作为我们的中心，如果是大于 1 的奇数，我们取最中间那个，因为左右两端一定相等，而如果是偶数个，如果是2，我们就取这两个，如果是大于 2 的偶数，我们只取最中心的两个作为中心。

结合起来其实就是：

//palindrome(s, left, right)为延展判断回文串的函数
//i是当前位置

//第一种，如果中心是奇数个时，我们吧左右指针都指向当前位置，然后再延展
String s1 = palindrome(s, i, i);

//第二种，如果中心是偶数个，我们取中间两个，左右指针分别指向这两个，然后再延展
String s2 = palindrome(s, i, i + 1);

完整代码就是：

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) {
        return "";
    }
    //记录最长的回文子串
    String res = "";
    for(int i = 0; i < s.length(); i++) {
    	String s1 = palindrome(s, i, i);
    	String s2 = palindrome(s, i, i + 1);

res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }

return res;
}

//延展判断回文子串
public String palindrome(String s, int left, int right) {
    while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }

//返回该子串
    return s.substring(left + 1, right);
}

解决最长回文子串的方法除了有中心扩散方法，还有动态规划，动态规划是对暴力解法的优化。

回文子串，当去掉两头后，还是回文子串，所以，当我们要确定一个子串是否为回文子串时，就需要两个东西：

• 此时两端是否相等
• 去掉两端后是否还为回文子串

如果满足以上两个条件，此时的字串就是回文子串

这就是我们的状态。

状态就是此时 [i, j] 的子串是否为回文子串，

如果是：dp[i][j] = true
如果不是：dp[i][j] = false

而结合上面，我们的状态转移方程就可以推导出来了：

dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)

//dp[i + 1][j - 1]就是去掉两端后的回文子串的状态

还需要确定几个细节问题，

• 对于单独一个字符来说，肯定是回文子串，所以在初始化dp数组时，应该将

  dp[i][i] = true
  

• 因为要去掉两端判断，当只有两个字符时，去掉后无法再进行判断，所以[i + 1, j - 1]的长度要大于等于2，即 j - 1 - (i + 1) > 1,即 j - i > 3

完整代码：

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) {
        return "";
    }
    //创建dp数组
    boolean dp[][] = new boolean[s.length()][s.length()];
    //初始化数组
    for(int i = 0; i < s.length(); i++) {
        dp[i][i] = true;
    }
    int maxLen = 1;
    int maxStart = 0;
    //从列先开始遍历，因为对于当前的状态要参考于斜下角的
    for(int j = 1; j < s.length(); j++) {
        for(int i = 0; i < j; i++) {
            //如果两端不相等，则为false
            if(s.charAt(i) != s.charAt(j)) {
                dp[i][j] = false;
            }
            else {
                //如果两端相等，且当前的长度是小于2的，则直接可以判断为回文子串
                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;
                maxStart = i;
            }
        }
    }
    //截取结果返回
    return s.substring(maxStart, maxStart + maxLen);
}