[LeetCode] 5. Longest Palindromic Substring

5. Longest Substring Without Repeating Characters

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: String、Dynamic Programming

一、題目

Given a string s, return the longest palindromic substring in s.
A string is called a palindrome string if the reverse of that string is the same of the original string.

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 consists of only digits and English letters.

二、分析

• 注意 palindrome string 的特性：
  • 當長度為 1 時，必為 palindrome string
  • 當長度為 2 時，兩個字元必須相同才為 palindrome string
  • 當長度 >2 時，palindrome string 必須滿足
    1. 最左邊的字元等於最右邊的字元，即 s[left] == s[right]
    2. 除去最左邊的字元跟最右邊的字元，必須為 palindrome string，
       即 s.substr(left+1, len-2) 為 palindromic。

三、解題

1. Dynamic Prograimming

• Time complexity: \(O(n^2)\)
• Space complexity: \(O(n^2)\)

string longestPalindrome(string s) {
    int n = s.length();
    string res;
    bool dp[n][n];
    memset(dp, false, sizeof(dp));
    int len = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            if (i == j) {   // 長度為 1
                dp[i][j] = true;
            } else if (j - i == 1) {    // 長度為 2
                dp[i][j] = s[i] == s[j];
            } else {        // 長度 > 2
                dp[i][j] = s[i] == s[j] && dp[i+1][j-1];
            }

            if (dp[i][j] && j - i + 1 > len) {    // 比較長度
                len = j - i + 1;
                res = s.substr(i, len);
            }
        }
    }
    return res;
}

回目錄 Catalog