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

为了解决这个问题，我们需要判断一个字符串 s 是否是另一个字符串 t 的子序列。子序列的定义是可以通过删除 t 中的某些字符，使得剩下的字符顺序与 s 完全一致。

方法思路

为了高效地解决这个问题，我们可以使用预处理和二分查找的方法。具体步骤如下：

这种方法的时间复杂度为 O(len(t) + len(s) * log len(t))，能够高效处理较大规模的输入。

解决代码

import sys
from bisect import bisect_left
from collections import defaultdict
def is_subsequence(s, t):
    if not s:
        return True
    pos_map = defaultdict(list)
    for idx, c in enumerate(t):
        pos_map[c].append(idx)
    j = 0
    for c in s:
        if c not in pos_map:
            return False
        lst = pos_map[c]
        pos = bisect_left(lst, j)
        if pos >= len(lst):
            return False
        j = pos + 1
    return True
def main():
    input = sys.stdin.read().split()
    n = len(input)
    for i in range(0, n, 2):
        s = input[i]
        t = input[i+1]
        if is_subsequence(s, t):
            print("Yes")
        else:
            print("No")
if __name__ == "__main__":
    main()

代码解释

这种方法确保了在处理大规模输入时的高效性，正确性也得到了保证。

转载地址：http://bdxfk.baihongyu.com/