回文子串的两种方法：「中心扩展」&「动态规划」

647. 回文子串

5. 最长回文子串

本篇文章将介绍判断回文子串相关的两种方法：「中心扩展」「动态规划」

回文字符串

首先介绍一下什么是回文字符串！

「正向和反向观察得到的字符串顺序是相同的」或者「关于中心对称的字符串」

下面举几个例子：

abcba
abccba

中心扩展法

基于回文字符串对称性的特点，我们可以采取从中心向两边扩展的方法，得到回文子串

当中心是b时，同时向左向右扩展一格，得到的子串为aba，仍然符合回文的性质

继续向左向右扩展一格，得到的子串不符合回文的性质，停止！！

所以：以b为中心，可以得到的回文子串有两个b和aba

但是，仅仅以单个字母为中心的方法会遗漏掉偶数回文子串的情况，如下图所示：

所以我们不仅需要遍历以单个字母为中心的情况，也要遍历以两个字母为中心的情况

总结：「中心扩展法」的思想就是遍历以一个字符或两个字符为中心可得到的回文子串

下面给出模版：


// 返回以 i, j 为中心的最长回文子串的左右边界 (返回值可以根据题目意思自行改变)
// 这里把「一个字符或两个字符为中心」整合了一下
// 如果是一个字符为中心的情况，只需要 i = j 即可
private int[] isPalindromic(String str, int i, int j) {
    // 保证 left 和 right 都在合法区间内 [0, str.length() - 1]
    while (i >= 0 && j < str.length()) {
        if (str.charAt(i) != str.charAt(j)) break;
        i--; j++;
    }
    return new int[]{i + 1, j - 1};
}

动态规划法

首先我们需要明确dp数组表示什么含义？

这里需要二维的dp[][]数组，dp[i][j]表示子串[i..j]是否为回文子串

当我们判断[i..j]是否为回文子串时，只需要判断s[i] == s[j]，同时判断[i-1..j-1]是否为回文子串即可

需要注意有两种特殊情况：[i, i] or [i, i + 1]，即：子串长度为 1 或者 2。所以加了一个条件限定j - i < 2

状态转移方程如下：


xxxxxxxxxx
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1])

下面给出模版：


xxxxxxxxxx
// 返回值根据题目要求自行改变
private void palindromic(String str) {
    int n = str.length();
    boolean[][] dp = new boolean[n][n];
    // 下面两层循环就是求所有子串的固定套路
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (str.charAt(i) == str.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                // 其他处理逻辑...
            }
        }
    }
}

回文子串

下面开始题目实战！！题目详情可见回文子串

这个题目要求字符串中所有回文子串的数目，我们只需要在判断是回文子串的时候，记录一下数量即可！

中心扩展法


xxxxxxxxxx
private int ans = 0;
public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        // 以单个字母为中心的情况
        isPalindromic(s, i, i);
        // 以两个字母为中心的情况
        isPalindromic(s, i, i + 1);
    }
    return ans;
}
private void isPalindromic(String s, int i, int j) {
    while (i >= 0 && j < s.length()) {
        if (s.charAt(i) != s.charAt(j)) return ;
        i--;
        j++;
        ans++;
    }
}

动态规划法


xxxxxxxxxx
public int countSubstrings(String s) {
    int ans = 0;
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (s.charAt(j) == s.charAt(i) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                ans++;
            }
        }
    }
    return ans;
}

耗时比较

第一行是「动态规划法」的提交情况；第二行是「中心扩展法」的提交情况

所以优先使用「中心扩展法」吧，「动态规划法」只是为了用来理解 DP 解题思想滴！！

最长回文子串

下面开始题目实战！！题目详情可见最长回文子串

这个题目要求最长的回文子串，我们只需要在判断是回文子串的时候，记录一下长度，然后选出最大的长度即可！

中心扩展法


xxxxxxxxxx
public String longestPalindrome(String s) {
    int[] res = new int[]{0, 0};
    for (int i = 0; i < s.length(); i++) {
        int[] sub1 = longestPalindromeHelper(s, i, i);
        int[] sub2 = longestPalindromeHelper(s, i, i + 1);
        if (res[1] - res[0] < sub1[1] - sub1[0]) res = sub1;
        if (res[1] - res[0] < sub2[1] - sub2[0]) res = sub2;
    }
    return s.substring(res[0], res[1] + 1);
}
// 返回以 i, j 为中心的最长回文子串的左右边界
private int[] longestPalindromeHelper(String s, int i, int j) {
    int n = s.length();
    while (i >= 0 && j < n) {
        if (s.charAt(i) != s.charAt(j)) break;
        i--;
        j++;
    }
    return new int[]{i + 1, j - 1};
}

动态规划法


xxxxxxxxxx
public String longestPalindrome(String s) {
    int left = 0, len = 0;
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (s.charAt(j) == s.charAt(i) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len < j - i + 1) {
                    len = j - i + 1;
                    left = i;
                }
            }
        }
    }
    return s.substring(left, left + len);
}

耗时比较

第一行是「动态规划法」的提交情况；第二行是「中心扩展法」的提交情况

所以优先使用「中心扩展法」吧，「动态规划法」只是为了用来理解 DP 解题思想滴！！