Palindrome 回文字符串就是指从前往后和从后往前读，都是一样的，比如“aabcbaa”。
注意区分子串和子序列，子串是连续的，子序列可以不连续
题型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：求字符串的最长回文子序列长度
方法：动态规划
思路：
这里我们定义一个二维数组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：打印字符串的最长回文子序列
方法：动态规划
思路：
在上一题的基础上，多加一个path的矩阵来跟踪哪些字母被选中，加到回文子序列中。
规则如下：
- 如果是两头相等的情况：标为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：打印字符串的最长回文子串和长度
方法：动态规划
Examples：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”
思路：
-
对于字符串长度大于2的情况：
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道“bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。根据这样的思路，用动态规划来解决问题。
用P(i, j)表示字符串s的第i个到第j个字母组成的串（表示为s[i : j]）是否为回文串：
image.png于是，可以得到动态规划的状态转移方程：
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（即子串长度）的最大值。
注意：在转移状态方程中，是从长度较短的字符串向长度较长的字符串进行转移的，因此要注意动态规划的循环循序。
代码如下：
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]:
# 当第i个和第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：个人笔记总结，供之后复习使用
