论.技术.Python.(新)零学Python作业第33讲:“双指针”追踪判断字符串子序列

小蜂队

0.判断子序列
给定字符串 s 和 t ，请编程判断 s 是否为 t 的子序列。
字符串的子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串（例如，"ace" 是 "abcde" 的子序列，而 "aec" 则不是）。

s = input("请输入字符串s：")
t = input("请输入字符串t：")
    
n = len(s)
m = len(t)
    
j = k = 0
while j < n and k < m:
    if s[j] == t[k]:
        j += 1
    k += 1
    
if j == n:
    print("字符串 s 是字符串 t 的子序列。")
else:
    print("字符串 s 不是字符串 t 的子序列。")

解析：代码清单的解题思路是利用了 “双指针” 追踪的方法。
j 和 k 是两个负责追踪匹配的指针，分别指向字符串 s 和 t 的初始位置，然后每次判断 s[j] 与 t[k] 是否相等，如果相等则两个追踪指针同时移动到下一个位置继续判断。
由于 “子序列” 的判定是允许中间 “删除一些字符”，因此每当 s[j] 与 t[k] 不相等的时候，k 指针移动到下一位，继续尝试匹配。
最终如果 j 等于字符串 s 的长度，也就说明了 s 整个字符串成功地被遍历了一遍，即证明 s 是 t 的子序列。

.yun.