LeetCode - 5 解題紀錄

題目： LeetCode - 5. Longest Palindromic Substring

題目說明

給一個字串，求此字串最長的回文子字串。

解題思路

回文的形式有兩種，一種是奇數個數，一種是偶數個數，所以我們使用一個迴圈遍歷 s，嘗試將字串中的每個端點當作回文的中間並找出回文的長度，找出最長的長度並記錄起始點即可。

參考解法

class Solution {
public:
    string longestPalindrome(string s) {
        _s = s, n = s.size();
        int len = INT_MIN, start, curLen;
        for(int i = 0; i < n; ++i)
        {
            curLen = max(getLength(i, i), getLength(i, i + 1));
            if(curLen > len) len = curLen, start = i - (curLen - 1) / 2;
        }
        return s.substr(start, len);
    }
private:
    string _s;
    int n;
    
    int getLength(int l, int r)
    {
        while(l >= 0 && r < n && _s[l] == _s[r]) --l, ++r;
        return r - l - 1;
    }
};