赞
踩
力扣链接
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
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 j-i <= 1:
dp[i][j] = True
res += 1
elif dp[i+1][j-1] == True:
dp[i][j] = True
res += 1
return res
力扣链接
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。(不要求连续)
和上一题的区别在于,上一题需要连续
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0]*len(s) for _ in range(len(s))]
for i in range(len(s)):
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][j-1], dp[i+1][j])
return dp[0][-1]
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。