5.最长回文子串

问题

传送门：https://leetcode.cn/problems/longest-palindromic-substring/description/

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

思路：动态规划

我们思考一下如何判定字符串s是否为回文串。显然，判定$s[0]=s[n-1]$是否成立，如果不成立，直接判定不是回文串；否则，转化为“判定字符串$s[1:n-2]$是否为回文串”的子问题。因此，我们构建数组dp，其中$dp[i][j]$表示字符串$s[i:j]$是否为回文子串。

如何进行状态转移呢？根据上面的分析，求解$dp[i][j]$时，判定$s[i]=s[j]$是否成立，如果成立进一步求解$dp[i+1][j-1]$即可。

到这里可以发现，dp数组的更新方向比较复杂，因此不妨采取自顶向下的备忘录式动态规划写法。

边界条件

需要考虑两种边界条件。对于$dp[i][j]$，

• 若$i=j$，单个字符必然是回文子串，因此$dp[i][j]=1$；
• 若$i+1=j$，则$dp[i][j]=\begin{cases} 0,\ & \mathrm{if} \ s[i] \ne s[j] \\ 1, & \mathrm{otherwise} \end{cases}$

状态转移

状态转移方程为

代码

class Solution {
public:
    int dp[1005][1005];
    string str;
    int DP(int i, int j) {
        if(dp[i][j] != -1)  return dp[i][j];
        if(i > j)   return dp[i][j] = 0;
        if(i == j)  return dp[i][j] = 1;
        if(i + 1 == j)  return dp[i][j] = str[i] == str[j] ? 1 : 0;
        if(str[i] == str[j])    return dp[i][j] = DP(i+1, j-1);
        return dp[i][j] = 0;
    }
    string longestPalindrome(string s) {
        memset(dp, -1, sizeof(dp));
        str = s;
        int i, j;
        for(i=0; i<s.size(); i++) {
            for(j=0; j<s.size(); j++) {
                dp[i][j] = DP(i, j);
            }
        }
        string ans = "";
        int len = 0;
        for(i=0; i<s.size(); i++) {
            for(j=i; j<s.size(); j++) {
                // cout<<dp[i][j]<<" ";
                if(dp[i][j] && j-i+1 > len) {
                    ans = s.substr(i, j-i+1);
                    len = j - i + 1;
                }
            }
            // cout<<endl;
        }
        return ans;
    }
};