题解 | #将最长回文子串近似转化为最长公共子串问题#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        string A_rev = A;
        reverse(A.begin(), A.end());
        int n = A.size();
        //dp[i][j]表示以s1[i]和s2[j]结尾的字符串的公共最大长度
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(A[i]==A_rev[j]){
                    if(i==0 || j==0) dp[i][j] = 1;
                    else dp[i][j] = dp[i-1][j-1]+1;
                }
		// 特殊判断是不是和自己匹配上了
                if(dp[i][j] > res){
			// j是A_rev中的匹配位置，befor_pos 表示了翻转前的位置
                    int before_pos = n-j-1;
			// 翻转前的位置+公共子串长度-1 应该等于当前匹配位置i,相等说明是可以更新答案的
                    if(before_pos+dp[i][j]-1 == i){
                        res = dp[i][j];
                    }
                }
            }
        }
        return res;

    }
};

题目要求最长回文子串，从回文串的定义，不难理解回文串要满足正着读反着读都一样的要求。所以我想把初始字符串s翻转，得到s_rev，此时找s的最长回文子串问题就“基本”转化为了找到s和s_rev的最长公共子串问题。需要注意这两个问题是“基本”相等，但并不完全相等，下面会给出例子。

对于最长公共子串问题，可以定义二维数组dp，判断字符串1和字符串2对应的字符是否相等，不难写出转移方程为：

dp[i][j] = dp[i-1][j-1]+1,我们在遍历两个字符串的过程中，更新dp数组，记录dp数组中出现的最大值，最终将最大值作为答案输出。

但是在更新答案的过程中，有一种情况是不能更新答案的，如果s = “abc123cba”，s_rev=“abc321cba”,字符串s和s_rev的最大公共子串是“abc”,但你会发现他其实并不是一个回文串，这是不满足我们计算最长回文子串的初衷的。出现错误的原因是字符串s中的前三个字符“abc”和最后三个字符“cba”翻转后的“abc”匹配上了，这是我们不希望的，因此在更新答案的时候，需要特殊判断匹配成功的字符串是不是原来的字符串！！！（第一遍做就卡这里了） 判断的方法就是利用索引加加减减，判断是否符合条件即可。（见注释）