【leetcode】5. Longest Palindromic Substring

題目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

思路：

正常思路，對每一個元素的左邊、右邊所有元素進行判斷，記錄最長回文子串的起始位置、結束位置和長度。時間複雜度   O ( n 2 ) \ O(n^{2})  O(n2)。

最高效思路：Manacher算法。時間複雜度O(n)。未實作。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() == 0) {
            return s;
        }
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (s[0] == s[1]) {
                return s;
            }
            else {
                return s.substr(0, 1);
            }
        }
        int begin = 0, end = 0;
        int max_len = 1;
        for (int i = 0; i < s.length() - 1; ++i) {
            if (s[i] == s[i + 1]) {
                int len = 2;
                int p = i, e = i + 1;
                --p; ++e;
                while (p >= 0 && e <= s.length() - 1 && s[p] == s[e]) {
                    len += 2;
                    --p; ++e;
                }
                if (len > max_len) {
                    max_len = len;
                    begin = p + 1;
                    end = e - 1;
                }
            }
            if (i < s.length() - 2) {
                if (s[i] == s[i + 2]) {
                    int len = 3;
                    int p = i, e = i + 2;
                    --p; ++e;
                    while (p >= 0 && e <= s.length() - 1 && s[p] == s[e]) {
                        len += 2;
                        --p; ++e;
                    }
                    if (len > max_len) {
                        max_len = len;
                        begin = p + 1;
                        end = e - 1;
                    }
                }
            }

        }

        return s.substr(begin, max_len);
    }
};
           

discuss區答案:

思路：正常方法。周遊每個字元時，從中間往兩邊擴（分奇數長度和偶數長度兩種），取其中最大Palindromic長度及起始位置即可。

class Solution {
public:
    int max_len = 0;
    int max_begin = 0;
    
    string longestPalindrome(string s) {
        int len = s.length();
        if (len < 2){
            return s;
        }
        
        for (int i = 0; i < len - 1; ++i){
            extendPalindrome(s, i, i); // assume odd length
            extendPalindrome(s, i, i+1); // assume even length
        }
        
        return s.substr(max_begin, max_len);
    }
    
    void extendPalindrome(string &s, int begin, int end){ // string一定要用引用形式，copy開銷太大
        while (begin >= 0 && end < s.length() && s[begin] == s[end]){
            --begin;
            ++end;
        }
        // 此處begin和end指向的位置是臨界位置，是不符合要求的
        if (end - begin - 1 > max_len){
            max_begin = begin + 1;
            max_len = end - begin - 1;
        }
    }
};