【leetcode】Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

---

动态规划题。时间和空间复杂度都是O(x²),有空再优化一番空间复杂度吧。

类似于最长递增子序列的思想，大循环n次，找长度分别为2,3,...,n的串中最长的回文子序列。比如当前i=3，那么对于s="cabad"，我就要找串"cab","aba","bad"中的最长回文字符串。

设置一个表dp[1005][1005]，其中dp[i][j]表示s[i,...,j]中最长回文字符串长度。整个算法就可以看作是在填这张表（其实个人感觉动态规划很多问题最后都是填表），而且每次是填一条对角线的。那么如果：

1.s[i] == s[j]，那么就看看s[i+1,j-1]是不是一个回文串，如果是，dp[i][j] = dp[i+1][j-1]+2;

2.s[i] != s[j],或者s[i+1,j-1]是不是一个回文串，那么dp[i][j] = max(dp[i+1][j],dp[i,j-1]);

比如s="ccabacd"，当考虑dp[1][5],即串cabac时，先看s[2,4]是不是回文串，发现时，所以dp[1][5] = dp[2][4]+2=3+2=5;当考虑dp[1][4]的时候，即串"caba"s[1]!=s[4]，那么dp[1,4]=max(dp[2,4],dp[1,3])=3；

代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int dp[1005][1005];
        int n = s.size();
        int begin = 0;
        int maxLen = 1;
        
        for(int i = 0;i < n;i ++)
            dp[i][i] = 1;

        for(int i = 1;i <= n;i++){
            //计算长度为i的串的最长回文序列长度
            for(int j = 0;j < n-i;j++){
                if(s[j] == s[j+i] && dp[j+1][j+i-1] == i-1){
                    dp[j][j+i] = i+1;
                    begin = j;
                    maxLen = i+1;
                }
                else{
                        dp[j][j+i] = dp[j+1][j+i] > dp[j][j+i-1]?dp[j+1][j+i]:dp[j][j+i-1];
                }
            }
        }

        return s.substr(begin,maxLen);
    }
};

上述代码实现时因为是每次填写一条对角线，所以和平常循环二维数组的代码略不同。i表示当前遍历到第几条对角线，j则是行号，那么j+i就是对角线上的第j个元素了。

提交的时候超时了一次，因为其实对角线是会越来越短的（分别是n-1,n-2,...,1），j每次循环只要到n-i行就可以了，因为下面的元素一定是被填好的了（如下图所示）。