判断子序列

题目要求

给定字符串 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"))

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案