[LeetCode][Medium] 5. Longest Palindromic Substring

Leetcode 網址: https://leetcode.com/problems/longest-palindromic-substring/

題目說明:

給定一個字串 s，請找出該字串 s 中最長的回文子字串。

Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"

解題說明:

該題有很多種解法，這邊主要介紹二種我比較喜歡的解法:

第一種是 Dynamic Programming，

假設我們有一個字串 S(l, r) 要判斷是否為回文，

因為回文的特性，所以 S(l - 1, r + 1) 勢必也要是回文，否則 S(l, r) 絕對不是回文。

例如: S(2, 5) 是否為回文必須要 S[2] == S[5] 而且 S(3, 4) 也是回文，

而 S(3, 4) 是否為回文則必須要 S[3] == S[4] ，而且 S(4, 3) 代表 right 小於 left，故不需理會。

透過以上，我們即可寫出一個 DP 的程式來解決這個問題，其空間跟時間複雜度皆為 O(n * n)。

第二種解法則是 Expand Around Center，

我們可以知道最長回文的長度不是奇數就是偶數 (這不是廢話嗎 XD)，

假設長度是奇數，那代表最長回文的正中間是一個字元，

假設長度是偶數，那代表最長回文的正中間是二個字元，

所以我們從字串中找出所有正中間的字元 (時間複雜度為 O(n))，

並藉由正中間字元的往外擴散去找回文 (時間複雜度為 O(n))，

透過以上，我們即可以寫出一個不需要額外空間的解法，其時間複雜度為 O(n * n)。

程式碼 (DP)

class Solution {
public:
    string longestPalindrome(string s) {
        bool table[1000][1000] = {0};
        int start = 0, maxLength = 1;
        for (int i = 0; i < s.length(); i++) {
            table[i][i] = true;
        }
        
        for (int length = 1; length < s.length(); length++) {
            for (int i = 0; i < s.length() - length; i++) {
                int j = i + length;
                table[i][j] = s[i] == s[j] ? (i + 1 > j - 1 ? true : table[i + 1][j - 1]) : false;
                if (table[i][j] && (j - i + 1) > maxLength) start = i, maxLength = j - i + 1;
            }
        }
        return s.substr(start, maxLength);
    }
};

程式碼 ( EAC)

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, maxLength = 1;
        for (int i = 0; i < s.length(); i++) {
            int length = max(getPalindromeLength(s, i, i), getPalindromeLength(s, i, i + 1));
            if (length > maxLength) start = i - length / 2 + (length % 2 == 0 ? 1 : 0), maxLength = length;
        }
        return s.substr(start, maxLength);
    }
    
    int getPalindromeLength(string s, int l, int r) {
        while (l >= 0 && r < s.length() && s[l] == s[r]) l--, r++;
        return r - l - 1;
    }
};

結果

Runtime: 80 ms, faster than 57.82% of C++ online submissions for Longest Palindromic Substring.

Memory Usage: 231.6 MB, less than 17.76% of C++ online submissions for Longest Palindromic Substring.