目录
任务
647. 回文子串
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
思路
这道题的DP思路不是很直观,dp表示的不是某区间的回文子串数目,dp[i][j]表示[i,j]是否是回文子串,如果是则加结果加一,遍历完整个区间后,得到整个区间每个子区间各种情况的回文子串,累加起来即是所求。
那么只有s[i] == s[j]时,区间长度为1 和为2时,直接赋True,区间长度大于2时,如果 dp[i+1][j-1] 为True,则dp[i][j]为True
注意初始化和遍历顺序
class Solution:
def countSubstrings(self, s: str) -> int:
#dp[i][j]表示[i,j]是否是回文子串
dp = [[False] * len(s) for _ in range(len(s))]
result = 0
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i] == s[j]:
if j-i <= 1:
dp[i][j] = True
result += 1
elif dp[i+1][j-1]:
dp[i][j] = True
result += 1
return result
516. 最长回文子序列
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
思路
该题比上题直观很多,dp[i][j]表示[i,j]范围内的最长回文子序列长度。s[i] == s[j]时,长度拓展2;不相等时,长度取dp[i+1][j]和dp[i][j-1]的最大值(因为不等时说明两边不能同时加入,就取一边加入后的最大值)。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
#dp[i][j]表示[i,j]范围内的最长回文子序列长度
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)): # i==j时表示单元素区间,此时为最长回文子序列长度为1
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][len(s)-1]
标签:子串,第九章,Part13,len,range,序列,动态,dp,回文
From: https://www.cnblogs.com/haohaoscnblogs/p/18391155