LeetCode 745. 前缀和后缀搜索

2023-01-17 HGNULB 约 12 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 745. 前缀和后缀搜索

题意分析

设计一个 WordFilter，构造时接收一个单词数组。之后会被反复调用 f(pref, suff)，返回同时以 pref 为前缀、以 suff 为后缀的那个单词的下标；有多个满足时返回最大的下标，一个都没有则返回 -1。

要什么：这是一道设计题，衡量标准不是单次运行的总耗时，而是构造与查询之间的代价分配。查询会被调用上万次，所以哪怕构造慢一些，也应当把查询压到尽可能低；这正是「预处理换查询」的典型场景。

「返回最大下标」这条要求看起来是个小细节，实则决定了数据结构的写法：如果用「键 → 下标」的映射，只要按下标从小到大的顺序写入，后写的自然覆盖先写的，最终留下的就是最大下标，一行额外代码都不用写。反过来若倒序遍历，就必须加「已存在则跳过」的判断。

约束透露的信号非常关键：单词数量在万级，但每个单词的长度不超过 10。长度这个上限小得离谱，意味着一个单词的所有前缀只有 $L + 1$ 个、所有后缀也只有 $L + 1$ 个，两两组合不过 $(L+1)^2 \le 121$ 种。「某个维度的规模被压到常数」几乎总是在暗示可以枚举该维度的全部可能。于是构造期把每个单词的全部 $(前缀, 后缀)$ 组合都登记一遍，总量约 $15000 \times 121 \approx 1.8 \times 10^6$，完全可以承受，而查询就退化成一次哈希命中。

反过来看为什么朴素做法不行：每次查询遍历所有单词、逐个用 startsWith 与 endsWith 检查，单次 $O(n \cdot L)$，上万次查询就是 $10^8$ 级别的字符比较，稳定超时。

边界：pref 或 suff 可能等于整个单词；两者也可能在单词上重叠（例如单词 "a"，前缀 "a" 与后缀 "a" 指向同一个字符），题面允许这种情况，所以不能写「前缀长度加后缀长度不得超过单词长度」这类校验；不同单词可能重复出现，此时最大下标那个胜出；查询的前后缀组合可能在任何单词中都不存在，必须返回 -1 而不是抛异常。

解法：预计算所有前后缀组合到哈希表

核心思路

先看暴力：f(pref, suff) 时从后往前扫描 words，第一个同时满足前缀与后缀条件的下标就是答案。单次查询 $O(n \cdot L)$，构造 $O(1)$。问题在于查询次数与单词数都在万级，乘起来就爆了。瓶颈是每次查询都重新做一遍全量匹配，而单词集合在构造后根本不会变——重复劳动完全可以被预处理吃掉。

那能不能只预处理一半？比如建一棵前缀树，查询时先用 pref 定位到子树、拿到所有以它开头的单词下标集合，再在集合里逐个验后缀。这确实能加速，但在极端数据下（例如所有单词都以同一个字符开头）集合大小仍是 $O(n)$，最坏没有改善。问题的根子在于前缀和后缀是两个独立的筛选维度，只按一个维度建索引，另一个维度就只能线性过滤。

既然如此，就把两个维度合成一个键来建索引。注意到单词长度 $L \le 10$，一个单词的前缀共 $L + 1$ 个（含空串）、后缀也共 $L + 1$ 个，组合数 $(L+1)^2$ 是个不超过 121 的常数。于是在构造期把每个单词的全部组合都算出来，存进哈希表：
\[\text{weight}[\ prefix + \texttt{"\#"} + suffix\ ] = \text{该单词的下标}\]
查询时把 pref 与 suff 按同样规则拼成键，一次哈希查找即可，$O(P + S)$（拼接与哈希的代价按字符串长度算，而长度不超过 10，实际就是常数）。

两个设计细节必须说清。

其一是分隔符 # 不可省略。若直接拼成 prefix + suffix，会产生歧义：单词 "ab" 的「前缀 "a" + 后缀 "b"」和「前缀 "ab" + 后缀空串」都拼成 "ab"，两条不同的语义撞进同一个键。插入一个不会出现在单词字符集里的分隔符（题面保证单词只含小写字母，# 安全），就能保证 $(prefix, suffix)$ 与键一一对应。

其二是遍历顺序承担了「取最大下标」的职责。外层 i 从 0 递增到 n - 1，同一个键被多个单词命中时，后写入的下标更大，put 直接覆盖，循环结束后表中留下的必然是最大下标。这里的不变量是：处理完第 i 个单词后，对任意键 k，weight[k] 等于所有下标不超过 i 且能产生键 k 的单词中最大的那个下标。

这是一次彻底的「构造期换查询期」交易：构造从 $O(1)$ 涨到 $O(n L^2)$（还要乘上字符串拼接的 $O(L)$），换来查询从 $O(nL)$ 降到常数。在「构造一次、查询上万次」的场景下，这笔交易极其划算。

解题步骤

用一个 Map<String, Integer> weight 作为唯一的成员状态。为什么只需要一张表：查询的全部信息都被编码进了键，不需要保留原始的 words 数组，也不需要任何辅助索引。

构造函数外层 i 从 0 递增遍历 words。为什么必须升序：升序遍历让后写覆盖先写，自动实现「多解取最大下标」；若倒序遍历，就必须改成 putIfAbsent 或显式判存在，多一层出错点。

内层枚举前缀长度 p 从 0 到 n，取 word.substring(0, p)。为什么上界是 n 而不是 n - 1：p = n 对应整个单词作为前缀，这是合法查询；漏掉它会让 f("apple", "e") 这类查询失败。为什么 p 从 0 开始：空前缀虽然在本题的查询约束下用不到，但把它一并登记不增加复杂度量级，且能让实现对「允许空前缀」的变体天然兼容。

再内层枚举后缀长度 s 从 0 到 n，取 word.substring(n - s)。为什么是 substring(n - s) 而不是 substring(s)：后缀是从末尾往前数 s 个字符，起点应当是 n - s；写成 substring(s) 得到的是「去掉前 s 个字符」的结果，只有在特定长度下才碰巧相同。

把 prefix + "#" + suffix 作为键、i 作为值写入表中。为什么用 #：它不属于小写字母集合，能保证键与 $(prefix, suffix)$ 一一对应；换成任何一个可能出现在单词中的字符都会引入歧义。

f(pref, suff) 用同样规则拼键，命中返回下标，未命中返回 -1。为什么用 getOrDefault 而不是先 containsKey 再 get：一次哈希查找即可完成「查询 + 兜底」，少一次哈希计算，代码也更短。

以 具体用例 words = ["apple", "ape"] 走一遍，然后查询 f("a", "e") 与 f("ap", "le")。

构造阶段，i = 0，word = "apple"，n = 5。
前缀集合是 ""、"a"、"ap"、"app"、"appl"、"apple" 共 6 个；后缀集合是 ""、"e"、"le"、"ple"、"pple"、"apple" 共 6 个。两两组合产生 36 个键，全部映射到 0。其中我们关心的几条是："a#e" → 0、"ap#le" → 0、"apple#apple" → 0。注意最后这条体现了前后缀可以完全重叠——键的语义只是「以它开头且以它结尾」，不要求两段在单词中不相交。

构造阶段，i = 1，word = "ape"，n = 3。
前缀是 ""、"a"、"ap"、"ape"；后缀是 ""、"e"、"pe"、"ape"。16 个组合全部映射到 1。这里出现了覆盖：键 "a#e" 之前的值是 0，现在被写成 1。这正是「升序遍历自动取最大下标」的体现——"apple" 和 "ape" 都以 a 开头、以 e 结尾，题目要求返回较大的下标 1。
而键 "ap#le" 不会被 "ape" 产生（"ape" 的后缀里没有 "le"），所以它仍保持为 0。

查询 f("a", "e")：拼键 "a#e"，表中存在，值为 1，返回 1。手工验证："apple" 与 "ape" 都满足条件，最大下标是 1，正确。
查询 f("ap", "le")：拼键 "ap#le"，表中存在，值为 0，返回 0。手工验证：只有 "apple" 同时以 "ap" 开头、以 "le" 结尾，正确。
查询 f("b", "e")：拼键 "b#e"，表中不存在，返回 -1。正确。

最后看一眼分隔符为什么必要。假设去掉 # 直接拼接："apple" 会同时产生键 "a" + "pple" = "apple" 与 "apple" + "" = "apple"，两者撞成同一个键还算无害；但 "ape" 会产生 "ap" + "e" = "ape"，而单词 "ape" 的「前缀 "ape" + 空后缀」也是 "ape"。更致命的是，若数组里还有单词 "a" 与 "pe"……在跨单词的场景下，一个查询 f("ap", "e") 拼出的 "ape" 可能命中一个实际上并不以 "ap" 开头的单词，返回错误下标。加上 # 之后，"ap#e" 与 "ape#" 是两个不同的键，歧义彻底消失。

代码实现

class WordFilter {
    // 单词长度较小，构造期可以枚举所有前缀和后缀组合，把查询直接变成 O(1) 字典命中。
    private final Map<String, Integer> weight = new HashMap<>();

    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int n = word.length();

            for (int p = 0; p <= n; p++) {
                String prefix = word.substring(0, p);
                for (int s = 0; s <= n; s++) {
                    String suffix = word.substring(n - s);
                    weight.put(prefix + "#" + suffix, i);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        return weight.getOrDefault(pref + "#" + suff, -1);
    }
}

type WordFilter struct {
    // 单词长度较小，构造期可以枚举所有前缀和后缀组合，把查询直接变成 O(1) 字典命中。
    weight map[string]int
}

func Constructor(words []string) WordFilter {
    weight := make(map[string]int)
    for i, word := range words {
        n := len(word)
        for p := 0; p <= n; p++ {
            prefix := word[:p]
            for s := 0; s <= n; s++ {
                suffix := word[n-s:]
                weight[prefix+"#"+suffix] = i
            }
        }
    }
    return WordFilter{weight: weight}
}

func (this *WordFilter) F(pref string, suff string) int {
    if idx, ok := this.weight[pref+"#"+suff]; ok {
        return idx
    }
    return -1
}

复杂度分析

时间复杂度：构造 $O(n L^3)$，单次查询 $O(P + S)$。凭什么：构造时每个单词产生 $(L+1)^2$ 个键，每个键的拼接与哈希都要遍历一遍长度约 $2L$ 的字符串，所以是 $n \cdot L^2 \cdot L$；代入 $L \le 10$、$n \le 1.5 \times 10^4$，约 $1.8 \times 10^7$ 次字符操作，构造期一次性付清。查询只做一次拼接与一次哈希查找，长度是查询串长之和，因为 $L \le 10$ 所以实际就是常数。相比暴力查询的 $O(nL)$，把上万次查询的总代价从 $10^8$ 压到了 $10^4$ 级。

空间复杂度：$O(n L^3)$。凭什么：哈希表里存了约 $n (L+1)^2$ 个键，每个键的长度约 $2L + 1$ 个字符，字符总量即为 $n L^3$；代入上界约 $1.8 \times 10^6$ 个键、$3 \times 10^7$ 个字符，是这个解法明确付出的代价。这是一次纯粹的空间换时间，若内存受限就必须改用双向字典树等更紧凑的结构。

关键点总结

「构造一次、查询很多次」的设计题，要主动把代价前移到构造期。判断标准是查询次数与数据规模的乘积——一旦它超过预处理的总量，预处理就是划算的。这条原则贯穿前缀和、稀疏表、字典树等一系列结构。

某个维度的上界小到可以枚举时，就直接枚举它。这里 $L \le 10$ 让 $(L+1)^2$ 退化成常数，于是「两个独立的筛选维度」被合并成「一个可枚举的复合键」。看到题面给出一个异常小的上界，第一反应应该是「它是不是在暗示我可以暴力展开这一维」。

复合键必须用不属于原字符集的分隔符。prefix + "#" + suffix 与直接拼接的区别不是风格，而是正确性：没有分隔符时不同的 $(前缀, 后缀)$ 对会撞成同一个键。这个坑在「二维状态压成字符串键」的场景里普遍存在。

让遍历顺序替你实现「取最大/最小」的要求。升序遍历 + 覆盖写入，天然得到最大下标；这比先收集全部候选再取极值更短、更快，也更不容易漏。反过来若必须倒序，就要换成 putIfAbsent 语义。

后缀的截取起点是 n - s 而不是 s，这是字符串题里最常见的一位之差；把「取长度为 s 的后缀」在心里翻译成「从倒数第 s 个字符开始到结尾」，就不会写反。

面试视角：这题面试官通常会先让你说清「为什么不能每次查询都扫一遍」，再问「构造期 $1.8 \times 10^6$ 个键的内存开销能接受吗，有没有更省的做法」。标准的进阶答案是把后缀与前缀拼成一个串再建字典树：对单词 w，把所有形如 w的某个后缀 + "#" + w 的串（共 $L + 1$ 个）插入一棵 Trie 并在路径上记录最大下标，查询时搜索 suff + "#" + pref。这样键数从 $O(nL^2)$ 降到 $O(nL)$，且 Trie 共享前缀进一步省空间。能主动给出「哈希暴力展开」与「Trie 合并串」两条路线并比较它们的时空取舍，是这道困难题该有的答法。

易错点总结

错误写法：键直接拼成 pref + suff，不加分隔符 → 用例 words = ["ab"]，构造时「前缀 "a" + 后缀 "b"」与「前缀 "ab" + 空后缀」都产生键 "ab"；查询 f("ab", "b") 拼出 "abb" 未命中返回 -1 尚且正确，但查询 f("a", "b") 与 f("ab", "") 无法区分，在多单词场景下会返回不属于该前缀的单词下标。

错误写法：外层 i 倒序遍历 words 且仍用 put 覆盖 → 用例 words = ["apple","ape"]，键 "a#e" 先被写成 1、再被写成 0，查询 f("a","e") 返回 0；题目要求返回最大下标 1。倒序遍历必须配 putIfAbsent。

错误写法：前缀枚举写成 for (int p = 1; p < n; p++) → 用例 words = ["apple"]，p = n 被漏掉，查询 f("apple", "e") 拼出的键从未被登记，返回 -1；正确答案是 0。整词作为前缀是合法查询。

错误写法：后缀写成 word.substring(s) → 用例 words = ["apple"]，s = 2 时得到 "ple"（去掉前两个字符）而不是期望的后缀 "le"，键表整体错乱；查询 f("ap", "le") 返回 -1，正确答案是 0。

错误写法：认为前缀与后缀不能重叠，于是加上 if (p + s > n) continue; → 用例 words = ["a"]，查询 f("a", "a") 中 p = s = 1、n = 1，被这个判断跳过，返回 -1；题面允许前后缀指向同一段字符，正确答案是 0。

错误写法：f 里先 containsKey 再 get，但两次拼接了不同的键（比如一次带 # 一次不带） → 任意用例下 containsKey 恒为假，永远返回 -1。用 getOrDefault 一次搞定可以从结构上杜绝这类不一致。

错误写法：保留 words 数组，查询时先哈希命中再回头验证 words[idx].startsWith(pref) → 逻辑上无害但多此一举，并且一旦验证条件写反（比如用 endsWith 验前缀）就会把正确答案否掉；键已经保证了语义，不需要二次校验。

错误写法：构造时用 Map<String, List<Integer>> 收集所有下标，查询时取列表最大值 → 用例 words 中有一万个相同单词时，同一个键挂着一万个下标，内存翻倍且查询退化成 $O(n)$；只保留最大值就够了，历史下标没有任何用处。

错误写法：Go 中把 Constructor 的返回值写成 WordFilter 但方法用值接收者 func (this WordFilter) F(...) → 本题因为 map 是引用类型而侥幸能过，但一旦结构体里加入标量字段，方法内的修改就作用在副本上；设计类题目应统一用指针接收者。

错误写法：分隔符选了小写字母（如 "z"） → 用例 words = ["az"]，「前缀 "a" + 后缀 "z"」拼成 "azz"，而「前缀 "az" + 空后缀」拼成 "azz"，两条语义再次相撞；分隔符必须取自单词字符集之外。

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	只按前缀一个维度建索引，是本题进阶解法所依赖的基础结构
211. 添加与搜索单词 - 数据结构设计	中等	查询串含通配符 `.`，无法预枚举，只能在 Trie 上做带回溯的 DFS
1268. 搜索推荐系统	中等	同为前缀查询的设计题，但要返回字典序最小的三个候选，需在 Trie 节点上维护有序表
648. 单词替换	中等	求每个词的最短匹配前缀，考的是在 Trie 上「一遇到词尾就停」的贪心
677. 键值映射	中等	前缀查询要返回权值之和而非下标，更新时需沿路径回溯修正差值
720. 词典中最长的单词	中等	要求路径上每个前缀都是完整单词，考的是在 Trie 上做条件受限的深搜
14. 最长公共前缀	简单	一次性求全体单词的公共前缀，纵向扫描即可，不需要任何索引结构