【C/C++】【leetcode 5】最长回文子串

leetcode 5

动态规划求解
vector> dp(n,vector(n)); // dp[i][j]表示从i到j是否是回文串

• 初始化：dp[i][i]=1只有一个字母必然是回文字符串，如果s[i]==s[i+1]，dp[i][i+1]=1。
• 动态转移方程： dp[i][j] = dp[i+1][j-1] & (s[i] == s[j]);

注意点

• dp[i][j]是由dp[i+1][j-1]得来，所以计算第i行时要知道第i+1行的值，倒着计算。
• substr(start,length):求子串函数

T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n < 2)return s;
        //dp[i][j]表示当前从i到j是否是回文串
        vector> dp(n,vector(n));
        for(int i = 0;i < n;++i)dp[i][i] = 1;
        string res = s.substr(0,1);//记录结果
        int tmp = 0;//记录长度
        for(int i = n-2;i >= 0;--i){
            if(s[i] == s[i+1]){
                dp[i][i+1] = 1;
                if(tmp < 2)res = s.substr(i,2);
            }
            else dp[i][i+1] = 0;
            for(int j = i + 2;j < n;++j){
                dp[i][j] = dp[i+1][j-1] & (s[i] == s[j]);
                if(dp[i][j] && (j - i + 1 > tmp)){
                    tmp = j - i + 1;
                    res = s.substr(i,tmp);
                }
            }
        }
        return res;
    }
};