龙华高端网站设计,网页设计与制作实例教程,如何做网站淘客推广,龙岩做网站设计公司一、回文子串#xff08;连续#xff09; 1.1 题目 给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串#xf…一、回文子串连续 1.1 题目 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1
输入s abc
输出3
解释三个回文子串: a, b, c示例 2
输入s aaa
输出6
解释6个回文子串: a, a, a, aa, aa, aaa提示
1 s.length 1000s 由小写英文字母组成 1.2 题目链接 647.回文子串 1.3 解题思路和过程想法 1解题思路 分析当前的匹配情况会受到之前元素的情况所影响且影响的方式是类似的考虑采用动态规划的策略。 # 数组以 i 为开端且以 j 为结尾的子串是否为回文子串的结果 dp[i][j] # 递推关系如果子串中间dp[i1][j-1]是回文子串且其两外侧元素相等则 dp[i][j] True # 初始化为便于最后判断与覆盖全部初始化为 False dp [[False]*length for _ in range(length)] result 0 # 遍历因为递推关系是从左下角往右上方向递推所以遍历方向——从下往上从左往右 2过程想法 最初想的是用一维动态规划数组但是实在找不到递推关系 1.4 代码
class Solution:def countSubstrings(self, s: str) - int:length len(s)# 数组以i为开端且以j为结尾的子串是否为回文子串的结果 dp[i][j]# 递推关系如果子串中间dp[i1][j-1]是回文子串且其两外侧元素相等则 dp[i][j] True# 初始化为便于最后判断与覆盖全部初始化为 Falsedp [[False]*length for _ in range(length)]result 0# 遍历因为递推关系是从左下角往右上方向递推所以遍历方向——从下往上从左往右for i in range(length-1,-1,-1):for j in range(i,length):if s[i] s[j]:if j-i 1: # 两种情况只有一个元素或两相同元素dp[i][j] Trueresult 1else: # 中间不止一个元素需结合中间子串的结果进行判断if dp[i1][j-1]:dp[i][j] Trueresult 1return result
二、最长回文子序列不连续 2.1 题目 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。 子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
示例 1
输入s bbbab
输出4
解释一个可能的最长回文子序列为 bbbb 。示例 2
输入s cbbd
输出2
解释一个可能的最长回文子序列为 bb 。提示
1 s.length 1000s 仅由小写英文字母组成 2.2 题目链接 516.最长回文子序列 2.3 解题思路和过程想法 1解题思路 分析当前的匹配情况会受到之前元素的情况所影响且影响的方式是类似的考虑采用动态规划的策略。 # 数组以i为开端且以j为结尾的子串中回文子串的长度为 dp[i][j] dp [[0]*length for _ in range(length)] # 递推关系若两外侧元素相等则 dp[i][j] dp[i1][j-1] 2 否则dp[i][j] max(dp[i][j-1], dp[i1][j]) # 初始化因为缺少 i j 的情况所以对这部分进行初始化 dp[i][i] 1 # 遍历因为递推关系是从左下角往右上方向、从下方往上方、从左方往右方递推所以遍历方向——从下往上从左往右 2过程想法 有上一题的铺垫这题会好做一些 2.4 代码
class Solution:def longestPalindromeSubseq(self, s: str) - int:length len(s)# 数组以i为开端且以j为结尾的子串中回文子串的长度为 dp[i][j]dp [[0]*length for _ in range(length)]# 递推关系若两外侧元素相等则 dp[i][j] dp[i1][j-1] 2# 否则dp[i][j] max(dp[i][j-1], dp[i1][j])# 初始化因为缺少 i j 的情况所以对这部分进行初始化for i in range(length):dp[i][i] 1# 遍历因为递推关系是从左下角往右上方向、从下方往上方、从左方往右方递推所以遍历方向——从下往上从左往右for i in range(length-1,-1,-1):for j in range(i1,length):if s[i] s[j]:dp[i][j] dp[i1][j-1] 2else: dp[i][j] max(dp[i][j-1], dp[i1][j])return dp[0][length-1]
