LeetCode - 5. Longest Palindromic Substring

Medium

5. Longest Palindromic Substring

題目

Given a string s, return the longest palindromic substring in s.

Example 1

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2

Input: s = "cbbd"
Output: "bb"

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

解題思路

經典區間 DP 題
核心在於判斷一段字串 i ~ j 是否為回文

• DP 定義：

  • dp[i][j]：代表 s[i...j] 是否為回文

• 枚舉方式：

  • 先枚舉長度 len
  • 再枚舉起點 i
  • 終點 j = i + len - 1

• 判斷條件：

  • 當 s[i] == s[j] 時，才有可能是回文
  • 接著檢查中間區間：
    • 若 len <= 2
      • 長度為 1 或 2，只要頭尾相同就是回文
    • 或是 dp[i+1][j-1] == true
      • 中間本身已經是回文

• 轉移：

  • dp[i][j] = true 若符合上述條件

• 同時維護最長回文：

  • 若目前長度 len 比 maxLen 大
    • 更新 maxLen
    • 記錄起點 maxStart

• 最後回傳：

  • s.substr(maxStart, maxLen)

Solution Code

Time Complexity
O(n^2)

Space Complexity
O(n^2)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n+1, vector<bool>(n+1, false)); // dp[i][j] 代表 i~j 之間是回文

        int maxLen = 1, maxStart = 0;
        for(int len = 1; len <= n; ++len){ // 枚舉最常迴文字串長度
            for(int i = 0; i + len - 1 < n; ++i){
                int j = i + len - 1; // 每次找字串頭 i ~ 尾 j

                if(s[i] == s[j]){ // 當 s[i] == s[j]，檢查中間是否有可能是回文
                    if(len <= 2 || dp[i+1][j-1]){ // len <= 2 直接就是回文，或是檢查 i+1 ~ j-1 是不是回文
                        dp[i][j] = true;

                        if(maxLen < len){
                            maxLen = len;
                            maxStart = i;
                        }
                    }
                }
            }
        }
        return s.substr(maxStart, maxLen);
    }
};