leetcode-5-字符串题-最长回文子串

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 动态规划
// store[i][j] 表示字符串下标i到j的子串是否回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        
        int n = s.size();
        vector<vector<bool>> store(n, vector<bool>(n, false));
        string res("");

        for(int len = 1; len <= n; ++len){
            for(int i = 0; i < n; ++i){
                int j = i + len - 1;
                if(j >= n) break;

                store[i][j] = s[i] == s[j] && (len == 1 || len == 2 || store[i+1][j-1]);
                
                if(store[i][j] && len > res.size()) res = s.substr(i, len);
            }
        }

        return res;
    }
};