回文子串与回文子序列？数量？最长的情况？

文章目录 回文子串求解方案数求解最值 回文子序列求解方案数求解最值(最大长度)

回文的情况就是，从左边读和从右边读是一样的，总的来说，就是关于中间是对称的在这里又分为 回文子串 和 回文子序列 两种题型 回文子串：要求在原来的字符串中由连续的元素组成回文子序列：可以删除原来的字符串中的某些元素，可以挑着来选元素 回文子串和回文子序列分为又细分为两种题型 求解方案数 与 求解最长的情况(长度+直接返回具体的元素) 回文子串

回文子串：其实限制很大，当端点不等，那么s[i]-s[j]直接不满足，如果相等，还得看这个s[i+1]-s[j-1]的情况！，所以强调的是一个是否的问题！

求解方案数

LCR.020.回文子串

思路分析：属于区间dp的问题

定义dp[i][j]表示原来的字符串s[i]-s[j]是否是回文子串 def countSubstrings(self, s: str) -> int: # 求解的是回文子串的数量 # 使用区间dp，d[i][j] 定义为 s[i]到s[j]是否是回文字符串 n = len(s) dp = [[0]*n for _ in range(n)] # 当相等的时候，dp[i][j] = dp[i+1][j-1],否则就是0 ans = 0 for i in range(n-1,-1,-1): dp[i][i] = 1 ans+=1 for j in range(i+1,n): if s[i] == s[j]: if j == i+1: # 长度为2的得先处理 dp[i][j] = 1 ans+=1 continue dp[i][j] = dp[i+1][j-1] if dp[i][j]: ans+=1 return ans 求解最值

5.最长回文子串

思路分析：可以参照这个上面那个求解方案数的思路

还是定义dp[i][j]为 原来的字符串s[i]-s[j]是否构成回文子串，遍历完一遍之后，我们再对这个二维的dp数组进行遍历，记录dp[i][j]==1,那么此时这个start = i ,end = j,记录长度最长的情况end-start+1的时候 class Solution: def longestPalindrome(self, s: str) -> str: # 直接暴力做法 n = len(s) # 还是老样子，定义dp[i][j]为s[i]到s[j]是否是回文子串 dp = [[0]*n for _ in range(n)] for i in range(n-1,-1,-1): dp[i][i] = 1 for j in range(i+1,n): if s[i]==s[j]: if j - i ==1: dp[i][j] = 1 else: dp[i][j] = dp[i+1][j-1] start,end = 0,0 maxlen = 0 # 开始遍历，这里有一个巧妙的地方就是: # 当dp[i][j] == 1的时候，回文子串的长度就是j-i+1 for i in range(n): for j in range(n): if dp[i][j] : l = j-i + 1 if l>maxlen: maxlen=l start=i end=j return s[start:end+1] 也可以用马拉车算法 回文子序列 求解方案数

730.统计不同回文子序列

思路分析：还是区间dp的思路

定义dp[i][j]为s[i]到s[j]的非空回文子序列的数量当nusm[i]==nums[j]时，dp[i][j]=dp[i+1][j-1] * 2 + 2,理论上是这个转移公式，但是得排除这个dp[i+1][j-1]里面还存在nums[i] 和 nums[j]对称的情况，如果需要减去对应重复的情况当不相等的时候dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] class Solution: def countPalindromicSubsequences(self, s: str) -> int: # 区间dp求解方案数的问题 # 定义dp[i][j] 为原来的序列中，s[i] 到 s[j]中 mod = 10**9 + 7 n = len(s) dp = [[0] * n for _ in range(n)] for i in range(n-1, -1, -1): dp[i][i] = 1 # 单个字符是一个回文子序列 for j in range(i+1, n): if s[i] == s[j]: # 找到左右边界，避免重复计数 left = i + 1 right = j - 1 # 找到第一个等于 s[i] 的字符 while left <= right and s[left] != s[i]: left += 1 # 找到第一个等于 s[j] 的字符 while left <= right and s[right] != s[j]: right -= 1 if left > right: # 没有重复字符 dp[i][j] = dp[i+1][j-1] * 2 + 2 elif left == right: # 只有一个重复字符，那么删除的是单独的nums[i] dp[i][j] = dp[i+1][j-1] * 2 + 1 else: # 有多个重复字符,存在重复计数的过程 dp[i][j] = dp[i+1][j-1] * 2 - dp[left+1][right-1] else: dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] dp[i][j] %= mod # 取模 if dp[i][j] < 0: dp[i][j] += mod # 确保结果是非负的 return dp[0][n-1] 求解最值(最大长度)

516.最长回文子序列

思路分析：区间dp

定义dp[i][j]表示是s[i]-s[j]的子序列的最大长度区别于回文子串的是与不是，这个子序列存在更大的可能性nums[i]==nums[j]，那么dp[i][j] = dp[i+1][j-1] + 2，否则就是只能选一个端点，dp[i][j] = max(dp[i+1][j],dp[i][j-1]) class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) dp = [[0]*n for _ in range(n)] # dp[i][j]定义的是原来的字符串中s[i]到s[j]之间的最长的回文子序列的最大长度 for i in range(n-1,-1,-1): dp[i][i] = 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+1][j],dp[i][j-1]) return dp[0][n-1]