647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:def countSubstrings(self, s: str) -> int:lenS = len(s)# dp[i][j]表示 [i,j]的字串是否是回文字符串dp = [[False for _ in range(lenS)] for _ in range(lenS)]# s[i],s[j] 不相同那么返回False#　s[i],s[j] 相同# 下标i和j相同，同一个字符 ->回文字符串# 下标i和j相差1，如aa ->回文字符串# 下标i和j相差大于1，那么检查[i+1,j-1]是否为回文# 遍历顺序从上到下从左到右for i in range(lenS-1,-1,-1):for j in range(i,lenS):charI = s[i]charJ = s[j]if charI == charJ:if i==j or j-i==1:dp[i][j] = Trueelse:dp[i][j] = dp[i+1][j-1]else:dp[i][j] = Falseres = 0for i in range(lenS):for j in range(lenS):if dp[i][j] ==True:res+=1return res

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:def longestPalindromeSubseq(self, s: str) -> int:# 回文子序列 不是连续的lenS = len(s)# dp[i][j]字符串s在范围内最长的回文子序列为dp[i][j]dp = [[0 for _ in range(lenS)]for _ in range(lenS)]# 初始化for i in range(lenS):for j in range(lenS):# 一个字符的字符串最长回文子序列为1if i==j:dp[i][j] = 1# 如果s[i] == s[j] 那么dp[i][j] = dp[i+1][j-1] + 2# 如果s[i] != s[j] 那么dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])# 遍历顺序从下到上，从左到右for i in range(lenS-1,-1,-1):for j in range(i+1,lenS):charI = s[i]charJ = s[j]if charI == charJ:dp[i][j] = dp[i+1][j-1]+2else:#  分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。# 加入s[j]的回文子序列长度为dp[i + 1][j]。# 加入s[i]的回文子序列长度为dp[i][j - 1]。dp[i][j] = max(dp[i+1][j],dp[i][j-1])return dp[0][lenS-1]