leetcode題解-5.最長回文子串

最長回文子串:link

1.題目分析

1.最容易想到的是從每個位置向兩邊擴充得到最長回文子串。

2.示例代碼

class Solution {
private:
    int start, len = 0;
    
    void extend_palindrome(const string& s, int i, int j){
        while(i >= 0 && j < s.size() && s[i] == s[j]){
            i--; j++;
        }
        if(len < j - i - 1){
            start = i + 1;
            len = j - i - 1;
        }
    }
public:
    string longestPalindrome(string s) {
        if(s.size() < 2)
            return s;
        for(int i = 0; i < s.size() - 1; ++i){
            extend_palindrome(s, i, i);
            extend_palindrome(s, i, i + 1);
        }
        return s.substr(start, len);
    }
};
           

3.另外的解法

1.最優的解法應該是mannacher算法

2.dp解法O(n2)的時間複雜度，dp先求解的順序有點講究。