LeetCode 5. 最长回文子串

LeetCode 5. 最长回文子串

思路：

枚举奇数个数和偶数个的回文串，然后枚举中心点，两边扩散。

代码：

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i = 0;i < s.size(); i++){
            //先枚举奇数长度的回文串
            int l = i - 1,r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
            if(res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);

            l = i,r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]) l--,r++;
            if(res.size() < r - l - 1) res = s.substr(l + 1,r - l - 1);
        }
        return res;
    }
};

思路： Dp 的方法

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 1) return s;
        string ans = s.substr(0,1);
        s = ' ' + s;
        int res = 0;
        vector<vector<bool>> f(n + 1,vector<bool>(n + 1,false));
        
        for(int j=1;j<=n;j++){
            for(int i=1;i<=j;i++){
                //只有一个字符
                if(i == j) f[i][j] = true;
                //两个字符相等
                else if(s[i] == s[j]){
                    if(i + 1 > j - 1 || f[i + 1][j - 1]) {
                        f[i][j] = true;
                        if(res < j - i + 1){
                            res = max(res,j - i + 1);
                            ans = s.substr(i,res);
                        }
                    }
                }
            }
        }
        return ans;
    }
};