判断子序列

题目要求

给定字符串 s 和 t ，判断 s 是否为 t 的子序列

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）

示例 1:
s = "abc", t = "ahbgdc"
返回 true.

示例 2:
s = "axc", t = "ahbgdc"
返回 false

思路分析

一种思路是从t中寻找长度和s相同的子序列，然后判断这些子序列中有没有和s相等的子序列。这虽然是一个可行的方案，但显然效率很差。

另一个思路是先对t进行分析，遍历t获得每一个字符的出现位置，最终将得到一个字符分布的信息，例如“ahbgdc”, 它的字符分布情况是

{
'a': [0], 
'b': [2], 
'c': [5], 
'd': [4], 
'g': [3], 
'h': [1]
}

得到这些字符分布情况后，就可以根据每个字符的所在位置来判断字符串s是否是t的子序列，假设a出现的位置都大于b出现的位置，那么字符串s一定不是字符串t的子序列，每个字符可以出现在很多个位置上，我们只要找到一个位置满足s是t的子序列就可以了。

以"abc" 为例，先找到a出现的位置，不论有多少个，只取第一个，记为pre_index，因为a的位置越靠前，留给bc的空间就越大，那么接下来从出现的位置中寻找第一个比pre_index大的位置并赋值给pre_index，为什么要找第一个，因为b的位置越靠前，留给c的空间就越大，最后从c的位置找到第一个比pre_index大的位置

示例代码

def is_sub_seq(s, t):
    char_info = get_char_info(t)
    pre_index = -1
    for item in s:
        # 如果t中不包含item这个字符
        index_lst = char_info.get(item)
        if index_lst is None:
            return False
        for index in index_lst:
            # pre_index是上一个字符可以出现的位置
            # 当前字符出现的位置中,找第一个比pre_index大的位置
            if index > pre_index:
                pre_index = index
                break
        else:
            # 如果循环正常退出
            return False

    return True


def get_char_info(t):
    info = {}
    for index, item in enumerate(t):
        info.setdefault(item, [])
        info[item].append(index)
    return info


if __name__ == '__main__':
    print(is_sub_seq("abc", "ahbgdc"))