二维dp——最长回文子串求解

题目

给你一个字符串s，找到s中最长的回文子串

思路

• 对于一个字符串，如果它的长度为1，那么必定是回文串。

• 考虑一般情况

如果一个字符串是回文串，那么去掉两端的字符一定也是回文串，比如ababa是回文，其中bab也是回文。那么可以设二维dp数组，dp[i][j]表示字符串从第i位到第j位是否构成回文串（i<=j）

那么，我们只需要填充这个二维表格，找到这个二维表格中“相距最远”的两个1（即代表最长的回文子串）

• 考虑如何递推填充二位dp数组

首先考虑基本情况，所有回文子串可以看作由长度为1的子串（构成长度为奇数的回文串）和长度为2的子串（构成长度为偶数的回文子串）两种基本情况扩展来。所以有

dp[i][i] = 1; (i>=0 && i<str.size())
dp[i][i+1] = (str[i]==str[i+1]) ? 1 : 0; (i+1 < str.size())

这样就填充了表格的中间和上边一大部分

	j	0	1	2	3	4
i		a	a	a	a	a
0	a	1	1
1	a		1	1
2	a			1	1
3	a				1	1
4	a					1

此时考虑填充剩下的部分，由于i<=j，所以只需填充上三角部分对应的矩阵即可，并且，我们考虑了基本情况即子串长度为1和长度为2的情况，只需从长度为3考虑，即j起始位置应该是i+2，同时要保证i和j不越界(0<i<=j<str.size())

• 考虑状态转移情况

如果str[i]==str[j]，那么从i到j构成的子串是否是回文串由去掉边界两个字符决定，即dp[i][j]==dp[i+1][j-1]，体现在表格上就是dp[i][j]左下角的元素。如果我们自上而下填充这个表格，会出现一个元素左下角元素未计算的情况，因此，考虑对i从下往上遍历，保证左下角元素存在（i从str.size()-2到0遍历）遍历行的同时，j从左向右遍历，填充一行向上，直到填充整个上三角。

	j	0	1	2	3	4
i		a	a	a	a	a
0	a	1	1	1	1	1
1	a		1	1	1	1
2	a			1	1	1
3	a				1	1
4	a					1

• 计算最长回文子串

得到二维dp数组后，从中找每行相距最远的两个1即为对应回文子串的边界下标。找最长回文子串的代码，复杂度O（n^2）

string res;
for(int i = 0;i<str.size();i++)
{
    for(int j = i;j<str.size();j++)
    {
        if(dp[i][j]==1 && j-i+1>res.size()) 
        {
            res = str.substr(i，j-i+1);
        }
    }
}
return res;

代码

string longestPalindrome(string s) {
    if(s.size()==1) return s;
    int len = s.size();
    vector<vector<int> >dp(len，vector<int>(len，0));
    string res;
    //初始化边界
    for(int i = 0;i<len;i++)
    {
        dp[i][i] = 1;
        if(i+1<len && s[i]==s[i+1]) dp[i][i+1] = 1;
    }

    for(int i = len-1;i>=0;i--)
        for(int j = i+2;j<len;j++)
            if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1];
        
    for(int i = 0;i<len;i++)
        for(int j = i;j<len;j++) 
            if(dp[i][j]==1 && j-i+1 > res.size()) res = s.substr(i，j-i+1);
    
    return res;
}