題目描述
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"
思路
根據(jù)題意，給出一個(gè)字符串 s，想讓我們找出 s 中的最長回文子串。題目包含兩個(gè)信息：首先，回文串代表一個(gè)字符串正序和倒序是一樣的；其次，子串代表是連續(xù)的字符不能跳躍。
對于求解這道題，我們可以用逆向思維來想一下，如果一個(gè)串是回文串則它有什么性質(zhì)。由于回文串正序和倒序是一樣的，因此它應(yīng)該是一個(gè)對稱的結(jié)構(gòu)。也就意味著，我們?nèi)サ艋匚拇牡谝粋€(gè)和最后一個(gè)字符，剩下的字符串應(yīng)該還是一個(gè)回文串，那么這也可以成為我們判斷回文串的一個(gè)標(biāo)準(zhǔn)。如果我們以 dp[i][j] 代表子串s[i: j] 是否是回文串（布爾值），則狀態(tài)轉(zhuǎn)移方程為：
dp[i][j] = dp[i + 1][j - 1] and (s[i] == s[j])
這樣一來，我們可以用動態(tài)規(guī)劃的方式求解。假設(shè) len(s) = N，那么我們需要構(gòu)造一個(gè) N * N 的矩陣，時(shí)間復(fù)雜度和空間復(fù)雜度都是 O(N^2)。該方法思路比較清晰且通用，但不算最優(yōu)解。對于空間復(fù)雜度，我們還可以繼續(xù)對其進(jìn)行優(yōu)化。
我們還可以換一種思路，那就是如何構(gòu)造一個(gè)回文串。答案是：固定中間字符，向左右兩側(cè)擴(kuò)散。當(dāng)然了這里需要注意的一點(diǎn)是，這個(gè)中間字符可能是一個(gè)也可能是兩個(gè)。當(dāng)回文串長度為奇數(shù)時(shí)這個(gè)中間字符就只有一個(gè)，反之就有兩個(gè)。因此，我們可以遍歷 s 中的所有字符，并以當(dāng)前字符作為中間字符（或當(dāng)前字符與下一個(gè)字符一起作為中間字符）向左右擴(kuò)散構(gòu)建回文串，取最長的那一個(gè)，就是我們想要的答案。這種思路下，我們不需要申請額外的空間，空間復(fù)雜度降為 O(1)
該思路需要一個(gè) helper function 用來進(jìn)行回文串?dāng)U散。假設(shè)以 i 和 j 代表中間字符左右兩側(cè)的指針，則擴(kuò)散的條件是 i，j 不越界且 s[i] == s[j]。
代碼參考
class Solution:
def longestPalindrome(self, s: str) -> str:
# T: O(N^2), S: O(1)
def palindrome(s, i, j) -> str:
"""中心擴(kuò)散尋找回文串"""
while i >= 0 and j < len(s) and s[i] == s[j]:
i -= 1
j += 1
return s[i + 1: j]
res = ""
for i in range(len(s)):
s1 = palindrome(s, i, i) # 長度為奇數(shù)的回文串
s2 = palindrome(s, i, i + 1) # 長度為偶數(shù)的回文串
res = s1 if len(s1) > len(res) else res
res = s2 if len(s2) > len(res) else res
return res
