判断子序列
easy
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,
"ace"
是"abcde"
的一个子序列,而"aec"
不是)。进阶:
如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
致谢:
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1:
输入:s = "abc", t = "ahbgdc" 输出:true
示例 2:
输入:s = "axc", t = "ahbgdc" 输出:false
提示:
0 <= s.length <= 100
0 <= t.length <= 10^4
- 两个字符串都只由小写字符组成。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) >= len(t):#s长度不小于t
return s == t
si = ti = 0#遍历s的指针和t的指针
while ti < len(t) and si < len(s):
if t[ti] == s[si]:#从t列表遍历去s中找s[si]对应的字符
si += 1#si向后移动一位
ti += 1
return si == len(s)#如果si移动到最后一位则证明全部找到对应字符
首先,代码检查s的长度是否大于等于t的长度,如果是,则判断s和t是否相等,如果相等则返回True,否则返回False。这是因为如果s的长度大于等于t的长度,但s和t不相等,那么s肯定不是t的子序列。
接下来,代码使用两个指针si和ti进行遍历。si指向s的当前字符,ti指向t的当前字符。在while循环中,如果当前的t字符与s字符相等,si向后移动一位。然后,无论是否相等,ti都向后移动一位。循环继续直到ti达到t的末尾或si达到s的末尾。
最后,代码检查si是否等于s的长度,如果相等,则证明所有的s字符都在t中按顺序出现,返回True,否则返回False。
这段代码的时间复杂度是O(len(t)),其中len(t)表示字符串t的长度。它使用两个指针进行遍历,并在循环中进行字符比较,直到其中一个指针达到末尾位置。
进阶:如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# 预处理t,构建字典data_structure
data_structure = {}
for i, char in enumerate(t):
if char not in data_structure:
data_structure[char] = []
data_structure[char].append(i)
# 检查s是否为t的子序列
prev_pos = -1
for char in s:
if char not in data_structure or not any(pos > prev_pos for pos in data_structure[char]):
return False
prev_pos = min(pos for pos in data_structure[char] if pos > prev_pos)
return True
该代码根据优化方案创建了一个字典data_structure
,并使用循环遍历字符串t
,将字符及其在t
中的位置信息存储在字典中。然后,使用另一个循环遍历字符串s
,对于每个字符,检查它是否存在于data_structure
中,并且存在大于prev_pos
的位置,如果满足条件,则更新prev_pos
为该位置列表中大于prev_pos
的最小值。如果成功遍历完s
中的所有字符,返回True
,否则返回False
。文章来源:https://www.toymoban.com/news/detail-532877.html
这个优化方案可以大幅减少字符比较的次数,并且更适合处理大量输入的情况。文章来源地址https://www.toymoban.com/news/detail-532877.html
到了这里,关于leetcode:判断子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!