題目鏈接：國(guó)際版，國(guó)內(nèi)版
公司：Meta
題目描述
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 中的最長(zhǎng)回文子串蓖租。題目包含兩個(gè)信息：首先缭保，回文串代表一個(gè)字符串正序和倒序是一樣的蘸朋；其次伊履，子串代表是連續(xù)的字符不能跳躍韩容。
對(duì)于求解這道題，我們可以用逆向思維來(lái)想一下唐瀑，如果一個(gè)串是回文串則它有什么性質(zhì)群凶。由于回文串正序和倒序是一樣的，因此它應(yīng)該是一個(gè)對(duì)稱(chēng)的結(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])
這樣一來(lái)当窗，我們可以用動(dòng)態(tài)規(guī)劃的方式求解够坐。假設(shè) len(s) = N，那么我們需要構(gòu)造一個(gè) N * N 的矩陣崖面，時(shí)間復(fù)雜度和空間復(fù)雜度都是 O(N^2)元咙。該方法思路比較清晰且通用，但不算最優(yōu)解巫员。對(duì)于空間復(fù)雜度庶香，我們還可以繼續(xù)對(duì)其進(jìn)行優(yōu)化。
我們還可以換一種思路简识，那就是如何構(gòu)造一個(gè)回文串赶掖。答案是：固定中間字符感猛，向左右兩側(cè)擴(kuò)散。當(dāng)然了這里需要注意的一點(diǎn)是倘零，這個(gè)中間字符可能是一個(gè)也可能是兩個(gè)唱遭。當(dāng)回文串長(zhǎng)度為奇數(shù)時(shí)這個(gè)中間字符就只有一個(gè)，反之就有兩個(gè)呈驶。因此拷泽，我們可以遍歷 s 中的所有字符，并以當(dāng)前字符作為中間字符（或當(dāng)前字符與下一個(gè)字符一起作為中間字符）向左右擴(kuò)散構(gòu)建回文串袖瞻，取最長(zhǎng)的那一個(gè)司致，就是我們想要的答案。這種思路下聋迎，我們不需要申請(qǐng)額外的空間脂矫，空間復(fù)雜度降為 O(1)
該思路需要一個(gè) helper function 用來(lái)進(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) # 長(zhǎng)度為奇數(shù)的回文串
s2 = palindrome(s, i, i + 1) # 長(zhǎng)度為偶數(shù)的回文串
res = s1 if len(s1) > len(res) else res
res = s2 if len(s2) > len(res) else res
return res
