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

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

方法思路

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

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

解决代码

import sysfrom bisect import bisect_leftfrom collections import defaultdictdef 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 Truedef 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/