备案网站查询,c2c有哪些,温州微网站制作公司电话,wordpress 目录表插件647. 回文子串
给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字符组成#…647. 回文子串
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
思路构建dp数组dp[i][j]代表s[i:j1] 是否为回文子串ij)。转移方程如果s[i]s[j], 此时分为三种情况如果 ij, 则显然为回文子串如果ij-1则显然也是回文子串aa如果ij-1,则dp[i][j]dp[i1][j-1] (回文子串的前后加上相同的字母仍然是回文串。初始化因为一个字母本身就是回文所以对角线的元素初始化为1其他则初始化为0。遍历顺序由转移方程当前元素依赖左下角的数据所以遍历顺序为从上到下从左到右. 使用result记录true的个数. class Solution:def countSubstrings(self, s: str) - int:dp [[False]*len(s) for _ in range(len(s))]for n in range(len(s)):dp[n][n] Trueresult 0for i in range(len(s) -1, -1, -1):for j in range(ilen(s)):if s[i] s[j]:if ij-1:result1dp[i][j] Trueelse:dp[i][j] dp[i1][j-1]if dp[i][j]:result 1return result 516. 最长回文子序列
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
思路与上题类似使用二维dp数组模拟字符串。dp[i][j]表示字符串s[i:j1]的最长回文子序列长度。当s[i]s[j],dp[i][j] dp[i1][j-1] 2, 如果不等于则考虑将其中一个放到开头或结尾时的最长子序列长度
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] 1for i in range(len(s)-1, -1, -1):for j in range(i1, len(s)):if s[i] s[j]:dp[i][j] dp[i1][j-1] 2else:dp[i][j] max(dp[i1][j], dp[i][j-1])return dp[0][-1]
