LeetCode 642. 设计搜索自动补全系统

2026-09-13 HGNULB 约 11 分钟

文章信息 2 个分类 7 个标签

分类

LeetCode 困难

题目描述

✅ 642. 设计搜索自动补全系统

题意分析

系统逐字符接收输入。每输入一个普通字符，都要返回以当前完整输入为前缀的历史句子，最多三条：先按出现频次降序，同频次再按字典序升序。

# 表示当前句子结束，此时才把整句频次加一，清空输入并返回空列表。空格是句子和前缀的一部分；即使当前没有匹配项，也要继续记录输入，以便结束时新增这句话。

解法一：频次表过滤并保留前三候选

核心思路

[!blue]

用 counts 保存整句的历史频次，用 prefix 保存本次已输入内容。收到普通字符后，将它追加到前缀，再扫描历史句子，只考虑以这个前缀开头的句子。

扫描过程中，让 best 始终保留“目前已扫描候选中的前三名”。遇到新候选时，先加入，再按频次降序、字典序升序排序，超过三项就删掉最后一项。原来被淘汰的句子已有至少三句排在它前面，新增候选不会让它变好，因此以后也不需要重新考虑。

每次排序的列表最多只有四项，而不是把所有匹配句子都收集后排序。由于使用统一且确定的比较规则，哈希表遍历顺序不会影响最终结果。

收到 # 时只做提交：给当前整句的计数加一，再重置前缀。普通字符不修改频次，避免把尚未完成的输入误计为历史句子。

解题步骤

初始化频次表，把相同句子的初始次数累加。

收到普通字符后追加到 prefix，扫描并筛选所有前缀匹配项。

每加入一个候选就排序，并将候选列表截到前三项。

收到 # 时更新整句频次、清空前缀，并返回空列表。

代码实现

class AutocompleteSystem {
    private final Map<String, Integer> counts = new HashMap<>();
    private String prefix = "";

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) {
            counts.merge(sentences[i], times[i], Integer::sum);
        }
    }

    public List<String> input(char c) {
        if (c == '#') {
            counts.merge(prefix, 1, Integer::sum);
            prefix = "";

            return new ArrayList<>();
        }

        prefix += c;
        List<String> best = new ArrayList<>();

        for (String sentence : counts.keySet()) {
            if (!sentence.startsWith(prefix)) {
                continue;
            }

            best.add(sentence);
            best.sort(
                    (a, b) -> {
                        int order = Integer.compare(counts.get(b), counts.get(a));

                        return order != 0 ? order : a.compareTo(b);
                    });

            if (best.size() > 3) {
                best.remove(3);
            }
        }

        return best;
    }
}

import (
    "sort"
    "strings"
)

type AutocompleteSystem struct {
    counts map[string]int
    prefix string
}

func Constructor(sentences []string, times []int) AutocompleteSystem {
    s := AutocompleteSystem{counts: map[string]int{}}
    for i, sentence := range sentences {
        s.counts[sentence] += times[i]
    }
    return s
}

func (s *AutocompleteSystem) Input(c byte) []string {
    if c == '#' {
        s.counts[s.prefix]++
        s.prefix = ""
        return []string{}
    }
    s.prefix += string(c)
    best := []string{}
    for sentence := range s.counts {
        if !strings.HasPrefix(sentence, s.prefix) {
            continue
        }
        best = append(best, sentence)
        sort.Slice(best, func(i, j int) bool {
            if s.counts[best[i]] != s.counts[best[j]] {
                return s.counts[best[i]] > s.counts[best[j]]
            }
            return best[i] < best[j]
        })
        if len(best) > 3 {
            best = best[:3]
        }
    }
    return best
}

复杂度分析

设历史不同句子数为 S，历史句子总字符数为 T，当前前缀长度为 P，最长历史句长为 L。

时间复杂度：普通输入的期望上界为 $O(P+S(P+L))$，包含前缀拼接、扫描匹配和字符串比较；每次候选排序规模最多为 4。# 提交为 $O(P)$，初始化为输入句子总字符数的线性期望时间。

空间复杂度：$O(T+P)$，用于历史句子及当前输入；候选列表只保存常数个引用。

关键点总结

[!green]

前缀筛选与排名是两步：先确认匹配，再比较频次和字典序。

只保留已扫描部分的前三名足以继续更新，淘汰项不可能因新增候选重新变好。

每个普通字符都按当前完整前缀重新查询，提交时才改变历史计数。

解法二：Trie 缓存每个前缀的前三句

核心思路

[!blue]

将历史句子存入 Trie，每个字符对应一条边。每个节点保存这个前缀下排名最高的三句话，current 指向当前输入对应的节点。普通字符输入只需沿一条边前进，再复制该节点的缓存结果，不必扫描全部历史。

若某条边不存在，当前前缀就没有匹配句子，继续追加字符也不会重新出现匹配，因此 current 保持为空直到本句结束。但输入缓冲仍要保存全部字符，之后提交时才能把新句子插入 Trie。

record(sentence, delta) 先增加整句频次，再从根沿这句话的每个前缀更新缓存。一次提交只会让这一句话排名上升，其他句子的相对顺序不变，因此新的前三名一定来自“旧前三名加上本句”。把本句加入候选后重新排序、保留三项即可；若它已经在缓存里，不能重复加入。

不属于这句话的前缀不受影响，所以只更新它经过的节点。这个维护方式依赖频次只增加：原来排在前三名之外的其他句子不会因此晋级。

收到 # 后记录整句，清空输入，并让 current 回到根节点。查询返回缓存列表的副本，避免调用方修改返回结果时影响内部缓存。

解题步骤

创建根节点、频次表和输入缓冲，初始化时逐句调用 record。

普通字符追加到缓冲；若当前节点存在，就沿对应边前进，否则保持为空。

当前节点不存在时返回空列表，存在时返回其前三缓存的副本。

收到 #，增加整句频次，从根创建或访问各个前缀节点，更新各节点的前三缓存。

清空输入并重置当前节点，等待下一句。

代码实现

class AutocompleteSystem {
    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        List<String> best = new ArrayList<>();
    }

    private final Node root = new Node();
    private Node current = root;
    private final Map<String, Integer> counts = new HashMap<>();
    private final StringBuilder prefix = new StringBuilder();

    public AutocompleteSystem(String[] sentences, int[] times) {
        for (int i = 0; i < sentences.length; i++) {
            record(sentences[i], times[i]);
        }
    }

    private void record(String sentence, int delta) {
        counts.merge(sentence, delta, Integer::sum);
        Node node = root;

        for (int i = 0; i < sentence.length(); i++) {
            node = node.children.computeIfAbsent(sentence.charAt(i), c -> new Node());

            if (!node.best.contains(sentence)) {
                node.best.add(sentence);
            }

            node.best.sort(
                    (a, b) -> {
                        int order = Integer.compare(counts.get(b), counts.get(a));

                        return order != 0 ? order : a.compareTo(b);
                    });

            if (node.best.size() > 3) {
                node.best.remove(3);
            }
        }
    }

    public List<String> input(char c) {
        if (c == '#') {
            record(prefix.toString(), 1);
            prefix.setLength(0);
            current = root;

            return new ArrayList<>();
        }

        prefix.append(c);

        if (current != null) {
            current = current.children.get(c);
        }

        return current == null ? new ArrayList<>() : new ArrayList<>(current.best);
    }
}

import "sort"

type autoNode struct {
    children map[byte]*autoNode
    best     []string
}
type AutocompleteSystem struct {
    root, current *autoNode
    counts        map[string]int
    prefix        []byte
}

func newAutoNode() *autoNode { return &autoNode{children: map[byte]*autoNode{}} }

func Constructor(sentences []string, times []int) AutocompleteSystem {
    root := newAutoNode()
    s := AutocompleteSystem{root: root, current: root, counts: map[string]int{}}
    for i, sentence := range sentences {
        s.record(sentence, times[i])
    }
    return s
}

func (s *AutocompleteSystem) record(sentence string, delta int) {
    s.counts[sentence] += delta
    node := s.root
    for i := 0; i < len(sentence); i++ {
        c := sentence[i]
        if node.children[c] == nil {
            node.children[c] = newAutoNode()
        }
        node = node.children[c]
        found := false
        for _, candidate := range node.best {
            if candidate == sentence {
                found = true
                break
            }
        }
        if !found {
            node.best = append(node.best, sentence)
        }
        sort.Slice(node.best, func(i, j int) bool {
            a, b := node.best[i], node.best[j]
            if s.counts[a] != s.counts[b] {
                return s.counts[a] > s.counts[b]
            }
            return a < b
        })
        if len(node.best) > 3 {
            node.best = node.best[:3]
        }
    }
}

func (s *AutocompleteSystem) Input(c byte) []string {
    if c == '#' {
        s.record(string(s.prefix), 1)
        s.prefix = s.prefix[:0]
        s.current = s.root
        return []string{}
    }
    s.prefix = append(s.prefix, c)
    if s.current != nil {
        s.current = s.current.children[c]
    }
    if s.current == nil {
        return []string{}
    }
    return append([]string{}, s.current.best...)
}

复杂度分析

时间复杂度：普通字符查询均摊为 $O(1)$，只追加字符、沿边并复制至多三个字符串引用。提交长度为 P 的句子需访问 P 个节点；计入字符串比较和哈希，每次提交的期望上界为 $O(PL)$，L 为此次更新涉及句子的最大长度。初始化为逐句调用 record 的总开销。

空间复杂度：$O(T+P)$，T 为所有不同历史句子的总字符数；Trie 节点、每节点的三个缓存引用及历史计数占 $O(T)$，当前输入另占 $O(P)$。

关键点总结

[!green]

缓存维护发生在提交时，普通输入只读取当前前缀节点。

只有一个句子的频次增加时，旧前三名与本句足以选出新前三名。

缺失前缀只能终止当前查询，不能丢弃仍在输入的新句子。

若规则改为降频或删除句子，缓存外的候选可能递补，当前维护规则就需要调整。

解法对比：

频次表法每次扫描历史，逻辑直接；Trie 法在提交时维护各前缀的前三名，使普通字符查询保持常数级。两种实现使用完全相同的排名和提交规则。

易错点总结

[!yellow]

频次相同时按字典序升序，空格也参与比较。

普通输入不能增加频次，只有 # 才把当前整句提交。

没有匹配项时仍要保存输入，提交后新句子才会进入历史。

提交后同时清空前缀并重置 Trie 当前节点；返回缓存时复制列表，避免暴露可变内部状态。

相似题目

题目	难度	关联与区别
1268. 搜索推荐系统	中等	都是按前缀推荐前三项；原题只按字典序，本题还按动态频次排序。
692. 前K个高频单词	中等	复用频次降序、字典序升序的排名规则，本题还要按正在输入的前缀过滤。
208. 实现 Trie (前缀树)	中等	进阶解用 Trie 缩小前缀查询范围，并在节点缓存推荐结果。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/53313501

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！