如何优化前缀匹配短词替换代码以解决超时错误？

你的代码超时的核心原因是双重循环的时间复杂度太高：遍历替换列表的每个词，再遍历文本的每个单词，时间复杂度为O(M*N)（M是替换列表长度，N是文本单词数），当数据量较大时，这种嵌套循环会导致运行时间过长。此外，原代码还存在两个无用操作：没有判断替换词长度是否小于原单词长度（替换词长度等于或大于时无需替换），以及用text[i][:len(j)]代替直接赋值j。

优化方案1：预处理替换列表+提前终止匹配 #

通过预处理替换列表，减少不必要的匹配次数，同时对每个单词的匹配过程提前终止：

1. 去重替换列表：避免重复处理相同的替换词
2. 按长度升序排序：优先检查更短的替换词，一旦找到符合条件的匹配（前缀相同且替换词更短），立即停止后续检查，因为更短的替换词已经满足需求
3. 遍历文本单词而非替换词：每个单词仅需遍历排序后的替换词，找到第一个匹配项就停止，减少循环次数

优化后的代码：

# 预处理替换列表：去重+按长度升序排序
replace_words = list(set(input().split()))
replace_words.sort(key=lambda x: len(x))
text_words = input().split()

result = []
for word in text_words:
    replaced = False
    for rep in replace_words:
        # 仅当替换词更短且是原单词前缀时才替换
        if len(rep) < len(word) and word.startswith(rep):
            result.append(rep)
            replaced = True
            break  # 找到最短匹配，无需继续检查更长的替换词
    if not replaced:
        result.append(word)

print(' '.join(result))

优化方案2：前缀树（Trie）匹配（适合超大规模替换列表） #

如果替换列表包含上万个甚至更多词汇，前缀树可以将每个单词的匹配时间从O(M)降低到O(L)（L是单词的字符长度），进一步提升效率：

1. 构建前缀树：将所有替换词存入前缀树，每个节点标记是否为替换词的结尾
2. 遍历文本单词：对每个单词，沿着前缀树遍历字符，一旦遇到标记为结尾的节点且该节点对应的替换词长度小于原单词长度，就用该替换词替换原单词，停止遍历

优化后的代码：

class TrieNode:
    __slots__ = ('children', 'is_end')  # 优化内存占用
    def __init__(self):
        self.children = {}
        self.is_end = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    return root

# 预处理替换列表并构建前缀树
replace_words = list(set(input().split()))
trie_root = build_trie(replace_words)
text_words = input().split()

result = []
for word in text_words:
    node = trie_root
    replacement = None
    for idx, char in enumerate(word):
        if char not in node.children:
            break
        node = node.children[char]
        if node.is_end:
            # 找到有效替换词：长度小于原单词
            if (idx + 1) < len(word):
                replacement = word[:idx+1]
                break  # 最短匹配，停止遍历
    result.append(replacement if replacement is not None else word)

print(' '.join(result))

效果对比 #

• 方案1适合替换列表规模较小的场景，实现简单，性能提升明显
• 方案2适合替换列表规模极大的场景，时间复杂度更低，运行速度更稳定

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