LeetCode 472：拼接单词查找算法超时的Trie优化咨询

1. 压缩Trie节点存储，减少查找开销 #

• 用数组替代哈希表存子节点：原Trie用字典存子节点，频繁访问时哈希计算、碰撞处理的开销很高。改成固定26个元素的数组（对应小写字母），直接通过ord(c) - ord('a')索引子节点，大幅降低查找耗时。
• 合并单字符重复路径：针对"aaaaa..."这类连续重复单字符的长串，在Trie节点里加一个repeat_count字段，记录连续重复的次数，不用逐个创建节点。比如连续5个'a'，节点存repeat_count=5，DFS时直接跳过对应长度的字符，减少递归次数。

2. DFS加剪枝与记忆化，避免重复计算 #

• 记忆化搜索：用哈希表缓存字符串指定索引位置的拼接结果（比如memo[i]表示从第i位开始能否拼成合法拼接词），遇到已经计算过的位置直接返回结果，不用重复走DFS分支。
• 提前终止无效路径：DFS时如果剩余字符长度不足以组成至少一个单词（比如剩余长度小于1），直接返回false；如果当前Trie节点标记了单词结尾，优先尝试从下一个位置启动新搜索，同时继续当前路径（可能存在更长的单词），但如果当前路径走了很久还没找到结尾，且剩余长度小于Trie节点记录的最短单词长度，直接剪枝。

3. 预处理输入数组，减少无效操作 #

• 按字符串长度排序：先处理短单词，再处理长单词。因为拼接词依赖更短的单词，短单词先加入Trie，判断长单词时不用考虑更长的单词（拼接要求至少两个更短单词）。
• 过滤短字符串：长度小于2的字符串不可能是拼接结果，直接跳过，不加入Trie也不参与判断。

4. 给Trie节点加辅助标记，精准剪枝 #

• 在Trie节点中记录min_len：即从该节点出发能组成的最短单词长度。DFS时如果剩余字符长度小于这个值，直接终止这条路径，不用继续遍历。
• 标记单词结尾时记录长度：找到单词结尾节点时，直接跳转到对应长度的下一个位置，减少逐个字符遍历的循环次数。

优化后的Trie节点示例代码 #

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 数组替代字典
        self.is_end = False
        self.min_len = float('inf')  # 当前节点出发的最短单词长度
        self.repeat_count = 1  # 连续重复字符的次数

核心优化效果 #

针对大量单字符重复的长串输入，原DFS会逐个字符递归，重复判断开销极大。优化后：

• 合并重复字符的Trie节点，直接跳过多个字符，减少递归层数；
• 记忆化缓存避免相同位置的重复计算；
• 基于min_len的提前剪枝，直接砍掉大量无效路径。

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