.net网站开发优点,湖南旅游十大必去景区,仿牌网站优化,tk域名注册网站一、判断子序列 1.1 题目 给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;ace是abcde判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, ... , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码
示例 1
输入s abc, t ahbgdc
输出true示例 2
输入s axc, t ahbgdc
输出false提示
0 s.length 1000 t.length 10^4两个字符串都只由小写字符组成。 1.2 题目链接 392.判断子序列 1.3 解题思路和过程想法 1解题思路 双指针遍历用两个指针分别遍历两个字符串若是两指针所指相同则两指针同时往后否则将指向“母字符串”的指针向后移动最后判断指向“子字符串”的指针是否到达其串后侧位置 动态规划用两层循环结构对比两字符串的元素外层遍历“子串”内层遍历“母串”。若是两指针所指的前一元素相同——s[i-1] t[j-1]则更新“以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度dp[i][j]” ——dp[i][j] dp[i-1][j-1]1若是二者不相等则dp[i][j]等于前值不做更新——dp[i][j] dp[i][j-1]最后判断dp[len(s)][len(t)]lens(s)即可。 2过程想法 一题多解才能融会贯通所学的知识 1.4 代码 1.4.1 双指针遍历
class Solution:def isSubsequence(self, s: str, t: str) - bool:# 利用双指针分别指向两个字符串point_s , point_t 0, 0# 遍历字符串 t while point_s len(s) and point_t len(t):# 若匹配则两指针都向后移一位if s[point_s] t[point_t]:point_s 1# 否则只有指针 t 向后移point_t 1# 若指针 s 到达最后则表明匹配成功return point_s len(s) 1.4.2 动态规划
class Solution:def isSubsequence(self, s: str, t: str) - bool:m,n len(s),len(t)dp [[0] * (n1) for _ in range(m1)]for i in range(1, m1):for j in range(1, n1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] dp[i][j-1]if dp[m][n] m:return Trueelse:return False
二、不同的子序列 1.1 题目 给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。
示例 1
输入s rabbbit, t rabbit
输出3
解释
如下所示, 有 3 种可以从 s 中得到 rabbit 的方案。rabbbitrabbbitrabbbit
示例 2
输入s babgbag, t bag
输出5
解释
如下所示, 有 5 种可以从 s 中得到 bag 的方案。
babgbagbabgbagbabgbagbabgbagbabgbag
提示
1 s.length, t.length 1000s 和 t 由英文字母组成 1.2 题目链接 115.不同的子序列 1.3 解题思路和过程想法 1解题思路 当前的匹配情况会受到之前元素的情况所影响且影响的方式是类似的考虑采用动态规划的策略。数组以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j] 递推关系若二者元素相匹配当前情况取决于 用或不用 当前的元素 dp[i][j] dp[i-1][j-1] dp[i-1][j] 若二者元素不匹配当前情况的结果与不用当前元素的情况相同 dp[i][j] dp[i-1][j] 图片来源代码随想录红色文字是自己加的 初始化由上述递推关系可知当前位置的填写是基于左上方和正上方的元素所以需要提前对首行首列进行初始赋值 # 首行没有母串直接赋值 0 dp[0][j] 0 # 首列没有子串即空子串赋值1 dp[i][0] 1 2过程想法 递推关系的式子着实是没想到 1.4 代码
class Solution:def numDistinct(self, s: str, t: str) - int:long,short len(s),len(t)# 以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]# 以母串位置为行坐标以子串位置为列坐标dp [[0]*(short1) for _ in range(long1)]# 递推关系若二者元素相匹配当前情况取决于 用或不用 当前的元素# 若匹配则dp[i][j] dp[i-1][j-1] dp[i-1][j]# 初始化由上述递推关系可知当前位置的填写是基于左上方和正上方的元素所以需要提前对首行首列进行初始赋值for j in range(short1): # 首行没有母串直接赋值 0dp[0][j] 0for i in range(long1): # 首列没有子串即空子串赋值1dp[i][0] 1for i in range(1,long1):for j in range(1,short1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] dp[i-1][j]else:dp[i][j] dp[i-1][j]return dp[long][short]
