代码随想录算法训练营第天 |
647.回文子串
https://leetcode.cn/problems/palindromic-substrings/description/
代码随想录
https://programmercarl.com/0647.回文子串.html#思路
516.最长回文子序列
https://leetcode.cn/problems/longest-palindromic-subsequence/
代码随想录
https://programmercarl.com/0516.最长回文子序列.html#思路
647. 回文子串
- dp[i][j]的定义
- 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
- 递推公式
- s[i]!=s[j] 说明两端不同 一定不是 dp[i][j]= Flase
- s[i]==s[j]：分类讨论情况
- i和j相同 同一个字符串一定是
- i-j==1 差一个也是回文字符串
- i-1>1 如果dp[i+1][j-1]是回文字符串 这个也一定是
- 初始化：全部为false
- 遍历顺序
- 遍历顺序由上面的依赖条件决定；这里dp[i+1][j-1]得到dp[i][j]。所以从左下向右上遍历
点击查看代码
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[False]*len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i]==s[j]:
if abs(i-j)<2:
dp[i][j] = True
res = res+1
else:
if dp[i+1][j-1]:
dp[i][j] = True
res = res+1
return res
516. 最长回文子序列
- 回文子序列和回文序列的区别：如果两个序列不一样的话，选取左右两侧的最大值；
- 即使内部的子序列不是回文序列也可以；只需要在相同时增加长度即可；
点击查看代码
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
max_length = 0
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i]==s[j]:
if i==j:
dp[i][j] = 1
else:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
if dp[i][j]>max_length:
max_length = dp[i][j]
# print(np.array(dp))
return max_length