代码随想录算法营Day51｜647.回文子串，516.最长回文子序列

647. 回文子串

这题用中心扩散法去计算字符串里有多少回文子串。

class Solution: def extend(self,s,i,j): res = 0 while i >= 0 and j<len(s) and s[i] == s[j]: res += 1 i-=1 j+=1 return res def countSubstrings(self, s: str) -> int: res = 0 for i in range(len(s)): res += self.extend(s,i,i) res += self.extend(s,i,i+1) return res 516. 最长回文子序列 class Solution: def longestPalindromeSubseq(self, s: str) -> int: 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]: 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]