Cinte's Leetcode Record
0%

5. Longest Palindromic Substring

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

5. Longest Palindromic Substring

Approach 3
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string longestPalindrome(string s) {
        pair<int, int> maxp{0, 1};
        int maxlen = 1;
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for(int i = 0; i < s.size(); ++i)
            dp[i][i] = true;
        for(int i = 0; i < s.size() - 1; ++i)
        {
            dp[i][i + 1] = (s[i] == s[i + 1]);
            if(dp[i][i + 1] && maxlen < 2)
            {
                maxlen = 2;
                maxp = pair<int, int>{i, 2};
            }
        }
        
        // 此处循环先j再i 是由于以下j为j - 1 而 i 为 i + 1
        // 如果先i 再 j，则i + 1永远不是i的前一任
        // 先j后i，则可以用i,i+1的base来处理
        // 也是不断拉长区间
        for(int j = 1; j < s.size(); ++j)
        {
            for(int i = 0; i < j; ++i)
            {
                if(i == j || j == i + 1)
                    continue;
                dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
                if(dp[i][j])
                {
                    maxp = j - i + 1 > maxlen ? pair<int, int>{i, j - i + 1} : maxp;   
                    maxlen = max(maxlen, maxp.second);
                }
            }
        }
        return s.substr(maxp.first, maxp.second);
    }
};

T(n) : O(n^2)
S(n) : O(n^2)

dp改 

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
class Solution {
public:
    string longestPalindrome(string s) {
        int m = s.size();
        vector<vector<bool>> dp(m, vector<bool>(m, false));
        int start{ 0 }, maxLength{ 1 };
        for(int i = 0; i < m; ++i)
            dp[i][i] = true;
        for(int i = 0; i < m - 1; ++i)
            if((dp[i][i + 1] = s[i] == s[i + 1]) && (maxLength = 2))
                start = i;
        for(int len = 3; len <= m; ++len)
        {
            for(int i = 0, j = i + len - 1; j < m; ++i, ++j)
            {
                if(dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1])
                {
                    start = i;
                    maxLength = len;
                }
            }
        }
        return s.substr(start, maxLength);
    }
};
##### approach4(很快)

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
26
27
28
29
30
31
class Solution {
public:
    string longestPalindrome(string s) {
        pair<int, int> maxP;
        int maxLen = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            auto lenO = extract(s, i, i);
            auto lenS = extract(s, i, i + 1);
            if (max(lenO.second, lenS.second) > maxLen)
            {
                if (lenO.second > lenS.second)
                    maxP = lenO;
                else
                    maxP = lenS;
                maxLen = maxP.second;
            }
        }
        return s.substr(maxP.first, maxP.second);
    }
private:
    pair<int, int> extract(string& s, int left, int right)
    {
        while (left >= 0 && right <= s.size() && s[left] == s[right])
        {
            --left;
            ++right;
        }
        return pair<int, int>{left + 1, right - left - 1};
    }
};

T(n) : O(n^2)
S(n) : O(1)

Approach 5: Manacher's Algorithm