论.技术.Python.(新)零学Python作业第33讲:“双指针”追踪判断字符串子序列
本帖最后由 小蜂队 于 2022-9-25 15:20 编辑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 == t:
j += 1
k += 1
if j == n:
print("字符串 s 是字符串 t 的子序列。")
else:
print("字符串 s 不是字符串 t 的子序列。")
解析：代码清单的解题思路是利用了 “双指针” 追踪的方法。
j 和 k 是两个负责追踪匹配的指针，分别指向字符串 s 和 t 的初始位置，然后每次判断 s 与 t 是否相等，如果相等则两个追踪指针同时移动到下一个位置继续判断。
由于 “子序列” 的判定是允许中间 “删除一些字符”，因此每当 s 与 t 不相等的时候，k 指针移动到下一位，继续尝试匹配。
最终如果 j 等于字符串 s 的长度，也就说明了 s 整个字符串成功地被遍历了一遍，即证明 s 是 t 的子序列。 {:10_257:}
页:
[1]