Coding Interview Prep · 课时

前缀搜索与 Starts-With

Q: 「前缀搜索与 Starts-With」这节课中我会学到什么？

添加 starts_with 方法：如果任何已插入单词共享给定前缀，则返回 true，并利用它实现自动补全建议。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

添加 starts_with 方法：如果任何已插入单词共享给定前缀，则返回 true，并利用它实现自动补全建议。

第 2 / 4 课13 个步骤

前缀搜索与 Starts-With 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 2 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

前缀查询的优势

Trie 树相对于哈希映射的决定性优势在于高效的前缀查询。前缀查询可以回答以下问题：“有多少个已存储单词以此前缀开头？”“所有以此前缀开头的已存储单词是什么？”或者简单地回答“是否存在以此前缀开头的单词？”。这些查询的复杂度为 O(p)，其中 p 是前缀长度，与已存储单词总数无关，因此 Trie 树非常适合 autocomplete 和搜索建议。

starts_with 方法

starts_with(prefix) 会在存在任何以给定前缀开头的已存储单词时返回成功结果。沿着前缀的每个字符遍历 Trie。如果所有字符都能在没有缺失边的情况下遍历完成，就说明该前缀存在，并且至少有一个单词以它开头。其实现与 search 完全相同，只是在遍历完成后立即返回，而不检查 is_end。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

t = Trie()
for w in ['hello','help','world','word']:
    t.insert(w)
print(t.starts_with('hel'))   # True
print(t.starts_with('wor'))   # True
print(t.starts_with('xyz'))   # False

autocomplete：查找具有某个前缀的所有单词

要实现 autocomplete，请先遍历到前缀的结尾节点，然后从该节点执行 DFS（或 BFS），收集从此处延伸出的所有单词。将此前缀添加到每个收集到的后缀前面，即可还原完整单词。该操作的复杂度为 O(p + W)，其中 W 是所有匹配单词的总字符数。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def autocomplete(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return []
            node = node.children[c]
        # DFS from prefix end node
        results = []
        def dfs(n, path):
            if n.is_end:
                results.append(prefix + path)
            for char, child in n.children.items():
                dfs(child, path + char)
        dfs(node, '')
        return results

t = Trie()
for w in ['apple','app','application','apply','apt']:
    t.insert(w)
print(t.autocomplete('app'))  # ['app','apple','apply','application']

返回排序后的建议

要实现按顺序排列的 autocomplete，请在 DFS 期间按照字母顺序遍历子节点（遍历 sorted(node.children.items())）。由于 children 存储在字典中，这会增加 O(字母表大小 × 深度) 的开销，但能保证结果按字典序排列。基于数组的 Trie 树总是按字母顺序遍历子节点，因为索引 0-25 本身就是有序的。

def dfs_sorted(node, prefix, results):
    if node.is_end:
        results.append(prefix)
    for char in sorted(node.children.keys()):  # alphabetical order
        dfs_sorted(node.children[char], prefix + char, results)

print('Iterating children in sorted order gives lex-sorted suggestions')

Top-K autocomplete 建议

要按频率获取前 k 条建议，请为每个节点添加一个计数值，记录以该节点结尾的单词被搜索过的次数。收集建议时，使用大小为 k 的最大堆。这样可以将 DFS 产生的 O(W) 结果集缩减为 O(k)，而不必实例化所有匹配项。现实中的搜索引擎会将 Trie 前缀遍历与频率数据结合起来，以快速生成相关建议。

为 LeetCode 208 实现 Trie

LeetCode 208“实现 Trie（前缀树）”明确要求实现：insert(word)、返回精确匹配布尔值的 search(word)，以及返回前缀匹配布尔值的 startsWith(prefix)。这是经典的 Trie 实现。请记住：search 要求 is_end=True；startsWith 只要求前缀路径存在。

class Trie:
    def __init__(self):
        self.root = {}
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['#'] = True  # '#' marks word end
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '#' in node
    
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node: return False
            node = node[c]
        return True

t = Trie()
t.insert('apple')
print(t.search('apple'))      # True
print(t.search('app'))        # False
print(t.startsWith('app'))   # True

使用“#”作为结尾标记（字典 Trie）

一种简洁的做法是使用嵌套字典存储 Trie，并用类似 '#' 的特殊哨兵键标记单词结尾，这样就不需要 TrieNode 类。这种实现紧凑且适合面试，但可读性略低于显式的 TrieNode 对象。两种实现都可以接受；在时间紧张时，字典版本编写起来更快。

使用 Trie 查找最长公共前缀

要查找字符串列表的最长公共前缀，请将所有字符串插入 Trie，然后从根节点开始遍历，只要满足以下条件，就沿着唯一存在的路径继续前进：(1) 当前节点恰好有一个子节点；(2) is_end 为假。当任一条件不再满足时停止。沿着这条路径得到的内容就是最长公共前缀。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def longest_common_prefix(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
    
    prefix = []
    node = root
    while len(node.children) == 1 and not node.is_end:
        char, node = next(iter(node.children.items()))
        prefix.append(char)
    return ''.join(prefix)

print(longest_common_prefix(['flower','flow','flight']))  # 'fl'
print(longest_common_prefix(['dog','racecar','car']))     # ''

替换单词问题

替换单词（LeetCode 648）要求：给定一个根词字典和一个句子，将句子中的每个单词替换为字典中与之匹配的最短根词。将所有根词插入 Trie。对于句子中的每个单词，遍历 Trie，直到找到一个根词结尾，然后返回该根词作为替换结果。如果没有匹配的根词，则保留原单词。该方法的复杂度为 O(总字符数)，优于 O(n × m) 的暴力方法。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def replaceWords(dictionary, sentence):
    root = TrieNode()
    for word in dictionary:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def find_root(word):
        node = root
        for i, c in enumerate(word):
            if c not in node.children: break
            node = node.children[c]
            if node.is_end:
                return word[:i+1]
        return word
    
    return ' '.join(find_root(w) for w in sentence.split())

print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))

映射求和对问题

映射求和（LeetCode 677）要求插入键值对，并返回所有键具有给定前缀的值之和。为每个 TrieNode 添加一个 val 字段。执行 insert 时，遍历到末尾并设置该值；执行求和查询时，遍历到前缀的结尾节点，并使用 DFS 对其下方所有 val 字段求和。另一种方法是在插入过程中将累计和存储到每个节点中，从而以 O(p) 的复杂度完成查询。

实现带有限结果数量的自动补全

在生产环境的自动补全系统中，当数千个单词都匹配某个前缀时，返回所有匹配单词并不现实。相反，您可以在 DFS 遍历过程中使用大小为 k 的最大堆，维护目前找到的得分最高的 k 个单词。如果某个 DFS 分支不可能包含得分位列前 k 的单词，就可以提前停止该分支（根据得分上界进行剪枝）。这样，对于需要 k 条建议的每次查询，复杂度为 O(p + k × log k)，比收集所有匹配结果高效得多。

快速检查

检验您对本课数据结构与算法——编程面试准备相关概念的理解。

在交互式课程中回答

课程回顾

本课您学习了：前缀匹配操作会遍历前缀路径，如果路径存在则返回真值，无需检查结束标记；自动补全的 DFS 会从前缀末尾节点开始，在向下遍历时逐个追加字符，从而收集所有单词；以及为节点增加计数或值可以支持求和查询和前 k 项建议。接下来，我们将在字典树中加入通配符和正则表达式匹配。

免费开始

用 AI 导师学习 Coding Interview Prep — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 90
课程: 360

免费开始学习查看完整课程

常见问题解答

「前缀搜索与 Starts-With」课时是免费的吗？

是的 — 「前缀搜索与 Starts-With」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「前缀搜索与 Starts-With」这节课中我会学到什么？

添加 starts_with 方法：如果任何已插入单词共享给定前缀，则返回 true，并利用它实现自动补全建议。你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 2 节课，共 4 节。

「前缀搜索与 Starts-With」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Coding Interview Prep