利用Python生成器解决判断子序列问题

Question #

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，“ace"是"abcde"的一个子序列，而 “aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = “abc”, t = “ahbgdc” 输出：true 示例 2：

输入：s = “axc”, t = “ahbgdc” 输出：false

Answer #

def isSubsequence(self, s, t):
  t = iter(t)
  return all(i in t for i in s)

Viewpoint #

生成器的遍历只能往前，本题的解法充分利用了这一点。其中"i in t"的效果与下面的代码功能相似：

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

在t中找到了val后，生成器会记信这个位置，下次再执行"i in t"的判断时，会继续往下找。生成器相当于提供了一个免费的带记忆的指针。

From #

https://leetcode.cn/problems/is-subsequence 深入理解迭代器和生成器

Links #