Palindrome 回文字符串就是指從前往后和從后往前讀，都是一樣的箱叁，比如“aabcbaa”肖揣。
注意區(qū)分子串和子序列拭嫁，子串是連續(xù)的可免，子序列可以不連續(xù)
題型1：判斷字符串是否為回文字符串
方法：雙指針
思路：
同時從字符串頭尾開始向中間掃描字串，如果所有字符都一樣做粤，那么這個字串就是一個回文浇借。采用這種方法的話，我們只需要維護頭部和尾部兩個掃描指針即可怕品。
代碼如下：
def isPalindrome(s):
if len(s) < 1:
return False
if len(s) == 1:
return True
front = 0
back = len(s) - 1
while front < back:
if s[front] != s[back]:
return False
else:
front += 1
back -= 1
return True
題型2：求字符串的最長回文子序列長度
方法：動態(tài)規(guī)劃
思路：
這里我們定義一個二維數(shù)組dp:
dp[i][j] 表示字符串 s[i ... j] 的最長回文子序列的長度妇垢。
計算dp[i][j] 分兩種情況：
s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2-
當s[i] != s[j]:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
image.png
image.png
代碼如下：
def longestPalindromeSubseq(s):
n = len(s)
dp = [ [0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
return dp[0][n-1]
題型3：打印字符串的最長回文子序列
方法：動態(tài)規(guī)劃
思路：
在上一題的基礎(chǔ)上，多加一個path的矩陣來跟蹤哪些字母被選中肉康，加到回文子序列中闯估。
規(guī)則如下：
- 如果是兩頭相等的情況：標為2
之后回過來找字母的時候，往左下角找 - 如果是“去頭”的情況（即dp[i][j] = dp[i+1][j]）：標為1
之后找字母的時候吼和，往正下方找 - 如果是“去尾”的情況（即dp[i][j] = dp[i][j-1]）：標為0
之后找字母的時候涨薪，往左邊找
（見下面的示意圖）
代碼如下：
def printlongestPalindromeSubseq(s):
n = len(s)
dp = [ [0]*n for _ in range(n)]
path = [ [None]*n for _ in range(n) ]
for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
# 如果是相等，標記為2
path[i][j] = 2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
# 如果是去頭,path上標記為0炫乓，如果是去尾標記為1
if dp[i][j] == dp[i+1][j]: # 去頭
path[i][j] = 1
elif dp[i][j] == dp[i][j-1]: # 去尾
path[i][j] = 1
# 從dp[0][n-1]開始往反方向走：
i = 0
j = n-1
ans = []
while i <= n-1 and j >= 0 and path[i][j] != None:
print(i, j)
if path[i][j] == 2: # 往左下角移動一格
i += 1
j -= 1
ans.append(s[i])
elif path[i][j] == 1: # 往左邊移動一格
j -= 1
ans.append(s[i])
elif path[i][j] == 0: # 往正下方移動一格
i += 1
ans.append(s[i])
return (''.join(str(s) for s in ans))
題型4：打印字符串的最長回文子串和長度
方法：動態(tài)規(guī)劃
Examples：
給定一個字符串 s刚夺，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000末捣。
示例 1：
輸入: “babad”
輸出: “bab”
注意: “aba” 也是一個有效答案侠姑。
示例 2：
輸入: “cbbd”
輸出: “bb”
思路：
-
對于字符串長度大于2的情況：
對于一個子串而言，如果它是回文串塔粒，并且長度大于 2结借，那么將它首尾的兩個字母去除之后，它仍然是個回文串卒茬。例如對于字符串 “ababa”，如果我們已經(jīng)知道“bab” 是回文串咖熟，那么 “ababa” 一定是回文串圃酵，這是因為它的首尾兩個字母都是“a”。根據(jù)這樣的思路馍管，用動態(tài)規(guī)劃來解決問題郭赐。
用P(i, j)表示字符串s的第i個到第j個字母組成的串（表示為s[i : j]）是否為回文串：
image.png于是，可以得到動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程：
P(i, j) = P（i+1, j-1）, if (Si == Sj)
也就是說，只有s[i+1: j-1]是回文串捌锭，且s的第i個和第j個字母相同時俘陷，s[i: j]才會是回文串。 對于字符串長度為1或者2的情況：
如果長度為1观谦，那么肯定是回文串拉盾，直接可返回本身；
如果長度為2豁状，只有兩個字母相同時捉偏，才是回文串，反之則返回第一個字母
這就是這個問題的邊界條件泻红。
最終的答案就是P(i, j) = True中 j - i + 1（即子串長度）的最大值夭禽。
注意：在轉(zhuǎn)移狀態(tài)方程中，是從長度較短的字符串向長度較長的字符串進行轉(zhuǎn)移的谊路，因此要注意動態(tài)規(guī)劃的循環(huán)循序讹躯。
代碼如下：
def longestPalindrome(s):
n = len(s)
if n < 2:
return s
dp = [ [False]*n for _ in range(n) ]
max_len = 1
start = 0
for i in range(n): #矩陣對角線全部為True
dp[i][i] = True
for j in range(1, n):
print('j', j)
for i in range(0, j):
print('i', i)
if s[i] == s[j]:
# 當?shù)趇個和第j個之間只隔一個字母或沒有字母時：
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = False
if dp[i][j]:
cur_len = j-i+1
if cur_len > max_len:
max_len = cur_len
start = i
print('length: ', max_len)
return s[start : start + max_len]
PS：個人筆記總結(jié)，供之后復(fù)習(xí)使用
