LeetCode 5. Longest Palindromic Substring [Medium] [C++] 解題筆記

這題給定一個字串 s ，要我們找到 s 的最長回文子串。

EX:

    Input: "babad"

    Output: "bab"
    Note: "aba" is also a valid answer.

想法:

        這題如果是用暴立法枚舉所有 substring的話會超時。這邊紀錄兩種可行的作法，

第一種我覺得比較直覺，就是將每個元素視為中心點然後往左右延伸一直到左右的元素不同，

這樣就可以找到以每個元素為中心展開所能得到的最長回文子串，比較需要注意的是回文中心有可能是單一個元素(奇數長度回文子串)

也有可能是兩個元素(偶數長度回文子串)，因此每個元素除了自己為中心展開以外，也要考慮加上右邊元素為中心做展開。

另一個方式是 DP，其實想法跟上面大同小異只是需要轉個彎，上面我們以每個字元作為中心向兩邊

展開，例如: "abba"，從 bb 展開，換句話說如果 "abba" 是回文的話那摸 "abba" 左右都往內縮一個字元

的子串也必定要是回文，因此可以得出 DP 狀態轉移方程: 

dp[i][j]: if i ~ j is palindrome or not

dp[i][j] = 1 , if i == j  (只有一個字元)

dp[i][j] = s[i] == s[j] , if j = i + 1 (兩個字元相鄰)

dp[i][j] = s[i] == s[j] && dp[i+1][j-1] , if j > i + 1 

(至少 3 個元素，則首尾(i and j) 要相等且左右往內縮一個字元的子串也要是 palindrome)

Complexity: O(n^2) time, O(1) / O(n^2) space

完整程式碼:

解法一:

class Solution {
public:
    // treat lth and rth elements as center then expand to two sides
    int getLen(const string& s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }
        // since l and r will extend one more char
        return r - l -1;
    }
    string longestPalindrome(string s) {
        int start = 0;
        int max_len = 0;
        for (int i = 0; i < s.size(); i++) {
            auto cur = max(getLen(s, i, i), getLen(s, i, i+1));
            if (cur > max_len) {
                max_len = cur;
                start = i - (max_len - 1) / 2;
            }
        }
        
        return s.substr(start, max_len);
    }
};

解法二(DP):

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) { return ""; }
        int n = s.size();
        // dp[i][j] represent that if i～j is palindrome
        int dp[n][n];
        int left = 0;
        int max_len = 1;
        for (int i = 0; i < s.size(); i++) {
            // all char itself is palindrome with len 1
            dp[i][i] = 1;
            for (int j = 0; j < i; j++) {
                // dp[j][i] = 1                               if i == j
                //          = s[i] == s[j]                    if i = j + 1
                //          = s[i] == s[j] && dp[j+1][i-1]    if i > j + 1
                dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
                if (dp[j][i] && i - j + 1 > max_len) {
                    left = j;
                    max_len = i - j + 1;
                }
            }
        }
                                                                                                           
        return s.substr(left, max_len);
    }
};