1 題目描述

找到最長的字串，該字串是回文的，也就是說，從左到右和從右到左是一樣的。

2 解法

2.1 暴力破解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isPalindrome(s: str, i: int, j: int) -> bool:
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

def longestPalindrome(self, s: str) -> str:
    best = ""
    n = len(s)
    for i in range(n):
        for j in range(i, n):
            if j - i + 1 > len(best) and isPalindrome(s, i, j):
                best = s[i:j+1]
    return best

2.2 由中心向外過展

從2.1的暴力破解法中有很多redundant computation。

  • 如果 s[i:j] 是回文，那麼 s[i+1:j-1] 往內的組合是回文
  • 如果 s[i:j] 不是回文，那麼 s[i-1:j+1]往外擴展時，也不會是回文

也因此，你會發現，如果我們鎖定一個中心點，然後往外擴展，當發現不是回文時，就立刻換下一個中心點。這樣的時間複雜度是O(n^2)。

  • O(N) 遍歷每個字元當作中心點
  • O(N) 每個中心點擴展，最大擴展長度是O(N)

Time complexity: O(N^2)

  • 最佳解法是O(N)當發現整個s不是回文時，立刻換下一個中心點。
  • 最壞的狀況是O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def longestPalindrome(self, s: str) -> str:
    res = ""
    resLen = 0
    for i in range(len(s)):
        # odd length 
        l, r = i, i 
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > resLen:
                res = s[l:r+1]
                resLen = r - l + 1
            l -= 1
            r += 1
        # even length
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > resLen:
                res = s[l:r+1]
                resLen = r - l + 1
            l -= 1
            r += 1
    return res

如果不想要太多重複的程式碼，也可以參考下面的寫法，只是有幾個注意的點：

  1. 在 getLen 的時候，要注意 -1 因為會多擴展一次後才發現不滿足
  2. 要注意 start = i - (cur - 1) // 2 是因為我們要找到回文的起始點，cur要先-1才可以同時滿足odd, even的情況
    • 例如 abba 的時候，i=1的時候cur=4，所以start = 1 - (4-1)//2 = 1 - 1 = 0，這樣才可以取到abba
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindrome(self, s: str) -> str:
    def getLen(l: int, r: int):
        while l >= 0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1    # 要注意 -1 因為會多擴展一次後才發現不滿足

    n = len(s)
    start = 0
    ansLen = 0
    for i in range(n):
        cur = max(getLen(i, i), getLen(i, i+1))
        if cur > ansLen:
            ansLen = cur
            start = i - (cur - 1) // 2
    return s[start: start+ansLen]

2.3 O(n) Manacher’s Algorithm

我覺得這個算法非常複雜…我也不太懂，但是有興趣可以餐看這個影片Youtube |EP292Longest Palindromic Substring O(N) Manacher’s Algorithm

3 總結

這題沒有太多dp的影子在裡面，這題的關鍵在當你意識到回文的時候，從中間往外去擴展，這可以讓你從O(N^3)縮短成O(N^2)。這題的時間複雜度是O(N^2)，空間複雜度是O(1)。