Leetcode-5 最长回文子串

动态规划

class Solution {
   
public:
    string longestPalindrome(string s) {
   
        int st = 0, L = 1;
        int len = s.size();
        bool dp[1100][1100];
        for(int i = 0; i < len; i ++) dp[i][i] = 1;	//长度为1的子串都是回文串
        for(int i = 2; i <= len; i ++) {
   	//枚举长度
            for(int j = 0; j + i - 1 < len; j ++) {
   	//枚举位置
                int k = j + i - 1;	//结束位置
                if(s[j] != s[k]) dp[j][k] = 0;	//如果两端字符不一致不回文
                else {
   
                    if(i <= 3) dp[j][k] = 1;	//长度为3或者2的都是回文
                    else dp[j][k] = dp[j+1][k-1];	//由之前状态推过来
                }
                if(dp[j][k]) st = j, L = i;	//更新长度和起始位置
            }
        }
        return s.substr(st, L);
    }
};