经典题型
例题1：回文子串 字符串s，统计并返回字符串s中回文子串的数目
提示： 回文字符串：正读和倒读都是一样的字符串，可以用 nums == nums[::-1] 进行判断； 子字符串：字符串中由连续字符组成的一个序列； 输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c" --- 输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
核心问题：
- 如何判断某一段字符串是否是回文字符串？
- 如何统计总的回文子串的数量？
解题思路关键点：
- 采用动态规划思想求解，时间复杂度为O(n^2)
- dp[i][j]表示坐标i到j的字符串，是否是回文字符串，可以通过s[i]==s[j]和dp[i+1][j-1]==True来判断，抓住这个关键点，就可以对原字符串的任意子串进行判断（具体图解见参考链接）
# 代码实现以及解释 class Solution: def countSubstrings(self, s: str) -> int: # 先将数组空间都赋值False dp = [[False] * len(s) for _ in range(len(s))] # 结果存储res res = 0 # 遍历的顺序很重要，从右下角开始遍历，且只需要遍历对角线上半部分 for i in range(len(s)-1, -1, -1): for j in range(i, len(s)): # 判断是否是回文串的条件 if s[i] == s[j] and (j-i<=1 or dp[i+1][j-1]): res += 1 dp[i][j] = True return res
例题2：最长回文子序列 字符串s，返回最长的回文子序列长度
提示： 子序列定义：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列 输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" --- 输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb"
核心问题：
- 回文子序列和回文子串有什么区别？在处理上有什么不同？
- 动态规划的递推公式是什么？
解题思路关键点：
- 采用动态规划思想求解，时间复杂度为O(n^2)
- 类似上面，dp[i][j]的值通过dp[i+1][j-1]来确定，但是这个前提是s[i]等于s[j]；当s[i]不等于s[j]时，分析dp[i][j]的值为max(dp[i+1][j], dp[i][j-1])（具体图解可见参考链接中的特定题目）
class Solution: def longestPalindromeSubseq(self, s: str) -> int: dp = [[0] * len(s) for _ in range(len(s))] # 对角线元素单独赋值1 for i in range(len(s)): dp[i][i] = 1 for i in range(len(s)-1, -1, -1): for j in range(i+1, len(s)): # 当s[i]==s[j]时，总长度加2 if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: # 取左边或者下边最大值 dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][-1]
拓展题型
# 回溯 + 动态规划 # 先判断每个子串是不是回文串，再进行遍历 def partition(self, s: str) -> List[List[str]]: n = len(s) res = [] dp = [[False] * n for _ in range(n)] for i in range(n): for j in range(i + 1): if (s[i] == s[j]) and (i - j <= 2 or dp[j+1][i-1]): dp[j][i] = True def helper(i, tmp): if i == n: res.append(tmp) for j in range(i, n): if dp[i][j]: helper(j + 1, tmp + [s[i:j + 1]]) helper(0, []) return res
def minCut(self, s: str) -> int: # 解题思路在于两边dp，第一遍前确定回文串；第二遍进行计算 n = len(s) g = [[True] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i + 1, n): g[i][j] = (s[i] == s[j]) and g[i + 1][j - 1] f = [float("inf")] * n for i in range(n): if g[0][i]: f[i] = 0 else: for j in range(i): if g[j + 1][i]: f[i] = min(f[i], f[j] + 1) return f[n - 1]
def maxProduct(self, s: str) -> int: def get_max(s): if len(s) == 0: return 0 dp = [[0]*len(s) for _ in range(len(s))] for i in range(len(s)): dp[i][i] = 1 for i in range(len(s)-1, -1, -1): for j in range(i+1, len(s)): if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) return dp[0][-1] def diff_str(s, i): str_b = str(bin(i)[2:].zfill(len(s))) res1, res2 = '', '' for i in range(len(s)): if str_b[i] == '0': res1 += s[i] else: res2 += s[i] return res1, res2 res = 1 for i in range(0, 2 ** len(s)): r1, r2 = diff_str(s, i) res = max(res, get_max(r1) * get_max(r2)) return res
总结
回文串可以有很多种题型的衍生，leetcode上搜“回文”会出现很多题目，以下是对自己做过的题型的总结；
1、回文串问题可以用动态规划的思想解决，关键是找到递推公式，用图示法来理解很重要！
2、回文串的遍历条件通常是以下格式：
for i in range(n-1, -1, -1): for j in range(i, n): # 转换公式；
3、对于变换的回文串问题，数组dp存储的数据，可以为最大最小值；也可以为bool形式，用于存储s[i:j] 是否是回文串，再利用bool值求特定的值（相当于分两步走，先判断是否是回文串，再求解需要的值，例如“分割回文串II”）
