文章目录
- 647.回文子串
- 动态规划
- 双指针法
- 516.最长回文子序列
647.回文子串
动态规划
dp[i][j]指的是s[i:j+1]这段是否是回文串，如果s[i]s[j]需要分三种情况来判断，如果ij或者j=i+1，那么就是回文串，否则还要看这中间的是否是回文串，中间的是否是回文串就要看dp[i+1][j-1]这个是否为True，因此递归的顺序应该是i从大到小，j从小到大。
class Solution:def countSubstrings(self, s: str) -> int:l = len(s)dp = [[False]*l for _ in range(l)]result = 0for i in range(l-1, -1, -1):for j in range(i, l):if s[i] == s[j]:if j - i <= 1 or dp[i+1][j-1]:result += 1dp[i][j] = Truereturn result
双指针法
这题动态规划有点浪费了，只需要对每个位置从中间往外推是否是回文串就行了，当然中间可能是一个字符为中心，也可以是两个字符为中心，分开讨论。
class Solution:def countSubstrings(self, s: str) -> int:ans = 0for i in range(len(s)):ans += self.cir(s, i, i)ans += self.cir(s, i, i+1)return ansdef cir(self, s, i, j):ans = 0while i>=0 and j <len(s) and s[i]==s[j]:i -= 1j += 1ans += 1return ans
516.最长回文子序列
和上一题动规思路查不太多。初始化的时候把单个字符的回文长度初始化，然后如果再遇到两个字符相同的就直接在内部最长回文子序列的基础上+2，如果不相等就在分别扔掉这两个字符的情况下找最大值。
class Solution:def longestPalindromeSubseq(self, s: str) -> int:l = len(s)dp = [[0]*l for _ in range(l)]for i in range(l):dp[i][i] = 1for i in range(l-1, -1, -1):for j in range(i+1, l):if s[i]==s[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return max(max(dp))