【Java练习题】最长回文子串

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

示例 1：

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

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

解题思路

解法一：动态规划法
（一）状态

f[i][j]表示s的第 i 个字符到第 j 个字符组成的子串，是否为回文串
（二）转移方程

如果s的第 i 个字符和第 j 个字符相同的话，且 i + 1, 到 j - 1 的子串也是回文串的话，f[i][j] 也为回文串
f[i][j] = f[i + 1][j - 1] and s[i] == s[j]
稍微要注意的是，如果 i == j 或者 i + 1 == j 的时候，也就是单个字符的子串和两个相邻字符的子串，就不需要f[i + 1][j - 1]了
如果s的第 i 个字符和第 j 个字符不同的话，f[i][j] 不是回文串
然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i 开始往后遍历，这样可以保证每个子问题都已经算好了
代码如下：

public String longestPalindrome(String s) {
    String res = "";
    int n = s.length();
    boolean[][] f = new boolean[n][n];
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || f[i + 1][j - 1])) {
                f[i][j] = true;
                if(j - i >= res.length()){
                    res = s.substring(i, j + 1);
                }
            }
        }
    }
    return res;
}

解法二：中心扩展法

思路
回文串一定是对称的
每次选择一个中心，进行中心向两边扩展比较左右字符是否相等
中心点的选取有两种
aba，中心点是b
aa，中心点是两个a之间
所以共有两种组合可能
left：i，right：i
left：i，right：i+1

public class Solution2020106 {
    
     public int n;
     public String s;
     
     // 中心扩展法
    private int centerExpend(int left,int right) {
           
            while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            
            return right - left - 1;
        }
       
    public String longestPalindrome (String zifu) {
        
        this.s=zifu;
            
        if( s.length() < 2){
            return s;
        }
        int start = 0,end = 0;
        n = s.length();
       
       
        for(int i = 0;i < n;i++){
            int len1 = centerExpend(i,i);
            int len2 = centerExpend(i,i+1);
            // 两种组合取最大回文串的长度
            int maxLen = Math.max(len1,len2);
            if(maxLen > end - start){
                // 更新最大回文串的首尾字符索引
                start = i - ((maxLen - 1) >>>1);
                end = i + (maxLen >>> 1);
            }
        }
        return s.substring(start,end+1);
    }
    
    

    public static void main(String[] args) {

      
        Solution2020106 so=new Solution2020106();
        System.out.println(so.longestPalindrome("abayuioppoiuy"));
        
    }

}

图解

中心扩散法.png

var longestPalindrome = function(s) {
    if(!s || s.length < 2){
        return s;
    }
    let start = 0,end = 0;
    let n = s.length;
    // 中心扩展法
    let centerExpend = (left,right) => {
        while(left >= 0 && right < n && s[left] == s[right]){
            left--;
            right++;
        }
        return right - left - 1;
    }
    for(let i = 0;i < n;i++){
        let len1 = centerExpend(i,i);
        let len2 = centerExpend(i,i+1);
        // 两种组合取最大回文串的长度
        let maxLen = Math.max(len1,len2);
        if(maxLen > end - start){
            // 更新最大回文串的首尾字符索引
            start = i - ((maxLen - 1) >> 1);
            end = i + (maxLen >> 1);
        }
    }
    return s.substring(start,end+1);
};

方法三：超级详解动态规划
“动态规划”的方法是非常重要算法思想，并且这道题也是很经典的动态规划问题，一些快速判断子串是否是回文的问题都以这道问题为基础。

解决这类 “最优子结构” 问题，可以考虑使用 “动态规划”：

1、定义 “状态”；
2、找到 “状态转移方程”。

记号说明：下文中，使用记号 s[l, r] 表示原始字符串的一个子串，l、r 分别是区间的左右边界的索引值，使用左闭、右闭区间表示左右边界可以取到。举个例子，当 s = 'babad' 时，s[0, 1] = 'ba' ，s[2, 4] = 'bad'。

1、定义 “状态”，这里 “状态”数组是二维数组。

dp[l][r] 表示子串 s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。即如果子串 s[l, r] 是回文串，那么 dp[l][r] = true。

2、找到 “状态转移方程”。

首先，我们很清楚一个事实：

1、当子串只包含 1 个字符，它一定是回文子串；

2、当子串包含 2 个以上字符的时候：如果 s[l, r] 是一个回文串，例如 “abccba”，那么这个回文串两边各往里面收缩一个字符（如果可以的话）的子串 s[l + 1, r - 1] 也一定是回文串，即：如果 dp[l][r] == true 成立，一定有 dp[l + 1][r - 1] = true 成立。

根据这一点，我们可以知道，给出一个子串 s[l, r] ，如果 s[l] != s[r]，那么这个子串就一定不是回文串。如果 s[l] == s[r] 成立，就接着判断 s[l + 1] 与 s[r - 1]，这很像中心扩散法的逆方法。

事实上，当 s[l] == s[r] 成立的时候，dp[l][r] 的值由 dp[l + 1][r - l] 决定，这一点也不难思考：当左右边界字符串相等的时候，整个字符串是否是回文就完全由“原字符串去掉左右边界”的子串是否回文决定。但是这里还需要再多考虑一点点：“原字符串去掉左右边界”的子串的边界情况。

1、当原字符串的元素个数为 3 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 1 个字符，它一定是回文串，故原字符串也一定是回文串；

2、当原字符串的元素个数为 2 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 0 个字符，显然原字符串也一定是回文串。

把上面两点归纳一下，只要 s[l + 1, r - 1] 至少包含两个元素，就有必要继续做判断，否则直接根据左右边界是否相等就能得到原字符串的回文性。而“s[l + 1, r - 1] 至少包含两个元素”等价于 l + 1 < r - 1，整理得 l - r < -2，或者 r - l > 2。

综上，如果一个字符串的左右边界相等，以下二者之一成立即可：
1、去掉左右边界以后的字符串不构成区间，即“ s[l + 1, r - 1] 至少包含两个元素”的反面，即 l - r >= -2，或者 r - l <= 2；
2、去掉左右边界以后的字符串是回文串，具体说，它的回文性决定了原字符串的回文性。

于是整理成“状态转移方程”：

dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))
或者
dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))
编码实现细节：因为要构成子串 l 一定小于等于 r ，我们只关心 “状态”数组“上三角”的那部分取值。理解上面的“状态转移方程”中的 (r - l <= 2 or dp[l + 1, r - 1]) 这部分是关键，因为 or 是短路运算，因此，如果收缩以后不构成区间，那么就没有必要看继续 dp[l + 1, r - 1] 的取值。

读者可以思考一下：为什么在动态规划的算法中，不用考虑回文串长度的奇偶性呢。想一想，答案就在状态转移方程里面。

具体编码细节在代码的注释中已经体现。

参考代码：

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        boolean[][] dp = new boolean[len][len];
        // abcdedcba
        //   l   r
        // 如果 dp[l, r] = true 那么 dp[l + 1, r - 1] 也一定为 true
        // 关键在这里：[l + 1, r - 1] 一定至少有 2 个元素才有判断的必要
        // 因为如果 [l + 1, r - 1] 只有一个元素，不用判断，一定是回文串
        // 如果 [l + 1, r - 1] 表示的区间为空，不用判断，也一定是回文串
        // [l + 1, r - 1] 一定至少有 2 个元素 等价于 l + 1 < r - 1，即 r - l >  2

        // 写代码的时候这样写：如果 [l + 1, r - 1]  的元素小于等于 1 个，即 r - l <=  2 ，就不用做判断了

        // 因为只有 1 个字符的情况在最开始做了判断
        // 左边界一定要比右边界小，因此右边界从 1 开始
        for (int r = 1; r < len; r++) {
            for (int l = 0; l < r; l++) {
                // 区间应该慢慢放大
                // 状态转移方程：如果头尾字符相等并且中间也是回文
                // 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
                // 否则要继续看收缩以后的区间的回文性
                // 重点理解 or 的短路性质在这里的作用
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > longestPalindrome) {
                        longestPalindrome = r - l + 1;
                        longestPalindromeStr = s.substring(l, r + 1);
                    }
                }
            }
        }
        return longestPalindromeStr;
    }
}

写完代码以后，请读者在纸上写下代码运行的流程，以字符串 'babad' 为例：