061 · Is Subsequence
My First Thoughts
嗯，这道题是考察 s 是否是 t 的子序列。
那么 t 会是长的，s 就是短的。
核心是两点：
s的字符都能在t中找到s的字符在t中出现的次序要一致
比如：
s = "abc"
t = "ahbgdc"不能只检查 a、b、c 是否都在 t 中，还要按照 a、b、c 的顺序找到它们。
我想想哈，其实应该是 s 的字符一个个过，t 的字符快速找。
可以准备两个指针：
target = 0
source = 0其中：
target指向s当前需要匹配的字符source指向t当前检查的字符
然后对于 s[target]，让 source 在 t 中不断往后找：
target = 0
source = 0
while source < len(t) and target < len(s):
s_char = s[target]
while source < len(t) and s_char != t[source]:
source += 1
if source == len(t):
return False
target += 1
source += 1
return TrueWhy That Is Not Enough
上面的代码逻辑上已经正确，而且两个指针都只会向前移动，时间复杂度也是线性的。
剩下的问题主要是表达方式有一点绕：
- 外层循环控制
s是否匹配完成 - 内层循环负责在
t中寻找字符 - 内层循环结束后，还要单独判断
t是否已经用完
其实不需要把“寻找下一个相同字符”写成一个单独的内层循环。
可以换一个角度：
source每次检查t的一个字符；只有匹配成功时，target才向前移动。
这样只用一层循环，就能表达相同的过程。
Final Idea
仍然保留原来的两个指针：
target = 0
source = 0只要两个字符串都还没有处理完，就比较当前字符：
s[target] == t[source]如果相等，说明成功找到了 s 当前需要的字符：
target += 1无论是否相等，t[source] 都已经检查过，所以 source 每一轮都要向后移动：
source += 1最后不需要专门判断是哪一个字符串先结束，只需要检查：
target == len(s)如果成立，说明 s 的每一个字符都已经按照顺序匹配成功。
这也自然处理了空字符串：如果 s == ""，一开始就有 target == len(s)，所以会返回 True。
Why It Works
source 从左到右扫描 t，每个字符只检查一次。
当：
s[target] == t[source]说明当前这个 t[source] 可以作为 s[target] 的匹配字符，于是 target 向后移动，开始等待 s 的下一个字符。
如果两个字符不相等，只移动 source，继续在 t 的后面寻找同一个 s[target]。
因为 source 永远不会回头，所以成功匹配到的字符在 t 中一定保持原来的先后顺序。
例如：
s = "abc"
t = "ahbgdc"扫描过程是：
a == a 匹配，target 前进
b != h 只让 source 前进
b == b 匹配，target 前进
c != g 只让 source 前进
c != d 只让 source 前进
c == c 匹配，target 前进最后 target == len(s)，说明 s 已经全部匹配，因此返回 True。
如果 source 先到达 t 的末尾，而 target 还没有到达 s 的末尾，就说明剩余字符无法找到，返回 False。
Code
def isSubsequence(s, t):
target = 0
source = 0
while target < len(s) and source < len(t):
if s[target] == t[source]:
target += 1
source += 1
return target == len(s)Complexity
| Time | \(O(n)\) - n 是 t 的长度；source 最多从头到尾扫描 t 一次 |
| Space | \(O(1)\) - 只使用了两个指针变量 |
Takeaway
判断一个字符串是不是另一个字符串的子序列时，可以让指针完整扫描较长字符串；遇到需要的字符时，才移动较短字符串的指针。这样既能找到所有目标字符，也能天然保证它们的顺序不变。
← Quiz