leetcodeT5最长回文子串题解

¶题目描述如下：

¶题解：

对于一个回文子串，比如“abjba”，去除首尾字符得到的“bjb”仍然是回文子串，由这样的结构容易想到动态规划。

s[i,j]表示i到j的子串。

s[i,j]是回文串的前提是s[i+1,j-1]是回文串且s[i]==s[j]，这也就能成立递归了。

直接开一个n*n的bool型数组IF[i] [j]，其值为1表示s[i,j]是回文串，否则不是，我们只需要考虑i<=j的情况就好了。

首先IF[i] [i]直接赋1，因为单个字符一定是回文串。

接着按照长度开始遍历，2~n，起始点均从0开始，注意边界。需要单独处理的是长度为2/3的子串**（只需要s[i]==s[j]）**，否则按照递归条件处理。

对于是回文串的子串，需要和已存储的最长回文子串进行比较。

如此则完成。

时间复杂度O(n^2)。

¶源代码：

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len == 1){
            return s;
        }
        int maxLen = 1;
        string maxs = "";
        maxs += s[0];
        vector<vector <bool>> IF(len, vector<bool>(len));
        for(int i=0;i<len;i++){
            IF[i][i] = true;
        }
        for(int l=2;l<=len;l++){
            for(int i=0;i<len;i++){
                int j = i + l -1;
                if(j > (len-1)){
                    break;
                }
                if(s[i] != s[j]){
                    IF[i][j] = false;
                }
                else{
                    if((j - i -1 < 2)){
                        IF[i][j] = true;
                    }
                    else{
                        if(IF[i+1][j-1]){
                            IF[i][j] = true;
                        }
                    }
                }
                if(IF[i][j]){
                    int length = j - i + 1;
                    if(length > maxLen){
                        maxs = "";
                        for(int k=i;k<=j;k++){
                            maxs += s[k];
                        }
                        maxLen = length;
                    }
                }
            }
        }
        return maxs;
    }
};

以上。