【Warrior刷题笔记】NC17 最长回文子串【动态规划】详细注释

最长回文子串

https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=117&&tqId=37789&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

题目

来源：牛客
链接https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=117&&tqId=37789&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

1.描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

2.示例

示例1
输入："ababc"
返回值：3
说明：最长的回文子串为"aba"与"bab"，长度都为3
示例2
输入："abbba"
返回值：5
示例3 输入："b"
返回值：1

解题思路

该题可以使用动态规划解决。考虑这样一个事实，如果一个字符串本身是回文串，那么把这个字符串掐头去尾之后依然是回文串，也即如果s的位置i到j（包含i,j）的子串是回文串，那么s的位置i+1到j-1的子串也必然是回文串。例如，axyzyxa是回文串，那么掐头去尾以后的字符串xyzyx也是回文串。

于是我们可以使用动态规划来解决该问题，我们用dp[i][j]表示s的位置i到j的子串是否是回文串，如果该子串是回文串，那么dp[i][j]=true，否则dp[i][j]=false。根据上一段的分析，显然有dp[i][j]为真的条件是dp[i+1][j-1]也为真，且s[i]==s[j]。再考虑边界条件，当i==j时，dp[i][j]显然为真，当i>j时，dp[i][j]显然为假。此外还要注意子串长度为i的情况，在这种情况下，只需要保证s[i]==s[j]，dp[i][j]即为真。

根据以上讨论，我们可以得到算法：
1.计算字符串长度m，初始化dp[i][j](0≤i<m,0≤j<m)为假，最长回文子串长度maxLen为0，最长回文子串ans为""；
2.从i=m-1，j=m-1开始遍历更新dp[i][j]，i不断递减，j不断递增，同时当dp[i][j]为真时更新最长回文子串长度及最长回文子串。
填表完成时的ans就是最长回文子串。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int m = s.size();//字符串长度
        vector<vector<bool>> dp(m,vector<bool>(m,false));//dp[i][j]表示s中位置i到j的子串是否是回文串
        int maxLen = 0;//最长的回文子串长度
        string ans;//答案
        for(int i = m-1; i >= 0; i--){//从m-1, m-1开始依次填表dp
            for(int j = i; j < m; j++){
                if(i==j) dp[i][j] = true;//若i==j，则dp[i][j]=false;
                else{//若i，j不相等
                    if(j-i==1) dp[i][j] = s[i]==s[j];//若位置i到j的子串长度为i，则dp[i][j]为真的条件是s[i]==s[j]
                    else dp[i][j] = s[i]==s[j] && dp[i+1][j-1];//否则dp[i][j]为真的条件是dp[i+1][j-1]为真且s[i]==s[j]
                } 
                if(dp[i][j] && maxLen<j-i+1){//如果s中位置i到j的子串是回文串
                   maxLen = j-i+1;//则更新最长回文串长度
                   ans = s.substr(i,j-i+1); //以及最长回文串
                } 
            }
        }
        return ans;//返回答案
    }
};