字符串子序列

"""
字符串子序列
给定字符串s1和s2，判断s1是否为s2的子序列:
两个字符串中仅包含英文小写字母。
字符串s2可能会很长，s1是个短字符串。
字符串的一个子序列是原始字符串删除一些(也可不删)字符，
而不改变剩余字符相对位置形成的新字符串。
比如，xzp是xyzop的一个子序列，而xpy不是。
"""

def get_char_index(s):
    """
    构建字符在字符串s中的索引字典。

    :param s: 输入的字符串
    :return: 字符索引字典，键为字符，值为该字符在字符串s中所有出现位置的列表
    """
    index = {}
    for i, item in enumerate(s):
        index.setdefault(item, [])
        index[item].append(i)
    return index

def is_subsequence(s1, s2):
    """
    判断字符串s1是否为字符串s2的子序列。

    :param s1: 待判断的子序列
    :param s2: 主字符串
    :return: 布尔值，如果s1是s2的子序列，则返回True，否则返回False
    """
    char_index = get_char_index(s2)
    pre_index = -1
    for item in s1:
        if item not in char_index:
            return False
        for index in char_index[item]:
            if index > pre_index:
                pre_index = index
                break
        else:
            return False
    return True

if __name__ == '__main__':
    s1 = "xzp"
    s2 = "xyzop"
    print(is_subsequence(s1, s2))