本文共 2429 字，大约阅读时间需要 8 分钟。

LeetCode.jpg

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。示例 1:s = "abc", t = "ahbgdc"返回 true.示例 2:s = "axc", t = "ahbgdc"返回 false.

切题

一、Clarification

无特别需要注意的边界条件

二、Possible Solution

1、常规双指针解法

指针 point_s 指向 s 第一个字符，指针 point_t 指向 t 第一个字符。逐一判断 point_s 所指向的字符是否在 t 中存在。

• 如果 s[point_s] != t[point_t] , point_t = point_t + 1, 继续对比t的下一个字符，s的第point_s个字符是否在t中

• 如果 s[point_s] == t[point_t] , point_s = point_s + 1 , point_t = point_t + 1, 继续对比s的下一个字符

2、借助迭代器和生成器

借助python迭代器和生成器的特性，可以进一步简化代码相应的不太好理解（相关说明见下方代码）

Python3 实现

常规双指针解法

# @author:leacoder # @des:  双指针解法 判断子序列class Solution:    def isSubsequence(self, s: str, t: str) -> bool:        # 判断 s 是否为 t 的子序列。        # 指针 point_s 指向 s 第一个字符，指针 point_t 指向 t 第一个字符。逐一判断 point_s 所指向的字符是否在 t 中存在。        point_s = 0        point_t = 0        length_s = len(s)        length_t = len(t)'''1、如果 s[point_s] != t[point_t] , point_t = point_t + 1, 继续对比t的下一个字符，s的第point_s个字符是否在t中2、如果 s[point_s] == t[point_t] , point_s = point_s + 1 , point_t = point_t + 1, 继续对比s的下一个字符。'''        while point_s < length_s and point_t < length_t:            if s[point_s] == t[point_t]:                point_s = point_s + 1            point_t = point_t + 1        # 最后通过point_s是否与length_s相等判断s 是否为 t 的子序列。        return point_s == length_s

借助迭代器和生成器

# @author:leacoder # @des:  借助迭代器和生成器 判断子序列class Solution:    def isSubsequence(self, s: str, t: str) -> bool:        # 判断 s 是否为 t 的子序列。        b = iter(t)  # 迭代器        return all(((i in b) for i in s ))

说明：为了便于理解代码扩展分析

def is_subsequence(s, t):    b = iter(t)   # 把 t 转化成了一个迭代器    print(b)    gen = (i for i in s)  # 产生一个生成器， 这个生成器可以遍历对象 s    print(gen)    for i in gen:        print(i)    gen = ((i in b) for i in s)    print(gen)    for i in gen:        print(i)    return all(((i in b) for i in s))

借助迭代器和生成器 .png

b = iter(b) ， 把列表 b 转化成了一个迭代器 gen = (i for i in s) 产生一个生成器， 这个生成器可以遍历对象 s，能够输出 1, 3, 5。 (i in b)可以联想到 for in 语句。

(i in b) ， 大致等价于

while True:    val = next(b)    if val == i:        yield True

巧妙地利用了成器的特性， next() 函数运行的时候， 保存了当前的指针。

那么((i in b) for i in s)可以理解为：遍历s中元素 i，并在b中查找元素 i 是否存在。 由于next() 函数和yield 生成器的特性,如果 b 存在 i 返回True并保存当前指针不存在返回False （下一次查找从保存的指针开始继续查找，直到s 或者 b 遍历结束），这些True或False产生一个迭代器。

最后的 all() 函数，判断一个迭代器的元素是否全部为 True， 如果是则返回 True， 否则就返回 False。

GitHub链接：

知乎个人首页：

简书个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101490306 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！