企业官网建设流程全解析

刷算法题刷到LeetCode 745的人，第一眼多半是蒙的：这题让我实现一个WordFilter，核心就一个方法public int f(String pref, String suff)，意思是要我在一堆单词里，快速找出“同时满足前缀匹配和后缀匹配”的单词下标。光看题目描述会觉得很简单，但坑全藏在“同时”和“最大下标”这几个字里。

这题我在面试前刷过，也在实际面试中被追问过，后来帮别人讲题时发现很多人卡住的点高度一致：要么不知道有Trie树这种解法，要么知道Trie但不知道怎么同时处理前缀和后缀。这篇文章不打算只贴代码，我会从题目意图、方案选型、完整实现到常见坑排查，把整道题拆开讲透。适合正在刷题准备面试的人，也适合想把Trie树和倒排思想一次弄明白的朋友。

1. 先把题意嚼碎：这道题到底在考什么

1.1 前缀匹配和后缀匹配不是“包含”关系

题目要求很直白：f(pref, suff)返回一个下标i，要求words[i]以pref开头、以suff结尾，并且在所有满足条件的单词里取下标最大的那个。注意关键词是“开头”和“结尾”，不是“包含”。

举个例子，words = ["apple", "appetite", "banana"]，查询f("app", "e")时，"apple"以"app"开头且以"e"结尾，满足条件；"appetite"虽然以"app"开头，但以"e"结尾的是"tite"里面的"e"，严格来说它结尾是"e"吗？是的，"appetite"最后一个字符是e，所以它也满足。这就容易产生混淆，所以一定要抓住“同时满足”这个核心。

这种双条件过滤在真实业务里很常见。比如通讯录里要筛选“姓张”且“手机尾号是1234”的联系人，前缀条件筛姓氏，后缀条件筛尾号，两个条件互相独立但必须同时成立。LeetCode 745其实就是把这个场景抽象成了算法题。

1.2 题目经典在什么地方

这道题不是单纯考字符串API调用，它考的是“如何设计一种数据结构，让多维度的匹配查询变得高效”。朴素做法是每次查询都遍历所有单词，用startsWith和endsWith判断，逻辑没错，复杂度就是O(N * L)，N是单词数量，L是单词长度。如果查询次数也大，直接超时。

所以核心矛盾是：单词数组是静态的，但f会被调用很多次。我们要在构造阶段把数据预处理成合适的索引结构，让每次查询尽量快。这和搜索引擎里“文档是静态的、查询是高频的，所以提前建倒排索引”的思路一模一样。

1.3 容易被忽略的边界条件

我把边界条件提前列出来，后面写代码时可以逐条对照：

• pref和suff都可能为空字符串。
• 单词数组中可能有重复单词，但下标不同，必须返回最大下标。
• 前缀长度或后缀长度大于单词长度时，必定不匹配。
• 一个单词如果本身满足条件，它的下标要参与答案竞争。

这些边界如果不提前设计好，写出来的代码很容易在空串、重复单词这类测试用例上翻车。

2. 三种方案逐个拆：暴力、Hash预计算、双Trie

2.1 暴力扫描：只适合小数据量找感觉

最直接的实现就是遍历words，依次判断：

public int f(String pref, String suff) { int ans = -1; for (int i = 0; i < words.length; i++) { if (words[i].startsWith(pref) && words[i].endsWith(suff)) { ans = i; } } return ans; }

这段代码没有任何技巧，胜在简单。如果单词数量很小、查询次数也很少，其实能过。但它有一个隐患：遍历顺序是从小到大的，ans会被不断覆盖成更大的下标，所以最后返回的是最大下标，这个细节倒是歪打正着没问题。问题在于复杂度，一次查询就是O(N * L)，当N到10000、查询次数也上万时，基本上就是超时预定。

我个人的建议是，第一遍写暴力不是为了提交，而是为了快速验证自己对题意的理解是否正确。拿几个简单用例跑一遍，确认“前缀开头、后缀结尾、返回最大下标”这三个点都符合预期，然后再去写优化方案，这样不容易在题意理解阶段出错。

2.2 HashMap预计算：思路简单但空间容易炸

这种方案的脑洞是：我能不能把所有可能被查询的“后缀 + 分隔符 + 前缀”组合直接存成哈希表的key，value就是对应单词的下标？查询时拼好key直接查表，时间复杂度甚至能到O(1)。

代码看起来会非常短：

class WordFilter { Map<String, Integer> map = new HashMap<>(); public WordFilter(String[] words) { for (int i = 0; i < words.length; i++) { String w = words[i]; int n = w.length(); for (int p = 0; p <= n; p++) { for (int s = 0; s <= n; s++) { String key = w.substring(n - s) + "#" + w.substring(0, p); map.put(key, i); } } } } public int f(String pref, String suff) { return map.getOrDefault(suff + "#" + pref, -1); } }

注意我在key里用#做分隔符。为什么必须加？因为如果直接拼成suff + pref，会出现歧义。比如pref="ab"、suff="c"，拼出来是"cab"，下次查询pref="ab"、suff="ca"，拼出来还是"cab"，两个不同的查询条件却拿到同一个key，结果必然错乱。加一个不可能出现在单词里的分隔符，就彻底消除歧义。

这个方案的致命伤是空间。每个单词要枚举所有前缀和后缀组合，数量大约O(L^2)。如果单词长度是1000，一个单词就要往map里插100万个key；如果单词长度是5000，直接爆炸。所以HashMap方案只适合单词很短、数量很少的场景。它作为思路发散去想挺好的，但面试时如果你只抛出这种方案，面试官大概率会接着问“如果单词很长怎么办”，然后你就被动了。

2.3 双Trie树：这题真正的主流解法

Trie树也叫前缀树，特别适合处理“前缀匹配”类问题。这道题有两大难点：一是要同时匹配前缀和后缀，二是要返回最大下标。双Trie的思路恰好能把两个难点分开解决。

• 一棵正序Trie：每个单词正常按顺序插入。每个节点存一个列表，记录“以当前节点路径为前缀的所有单词下标”。
• 一棵反序Trie：把每个单词反转后再插入。比如"apple"变成"elppa"插入。每个节点存的列表，记录“以当前节点路径为后缀的所有单词下标”。

查询时，前缀pref在正序Trie里找到对应节点，取出一个下标列表A；后缀suff反转后在反序Trie里找到对应节点，取出一个下标列表B。A和B的交集最大值，就是答案。

为什么这个方案空间上比HashMap好？因为每个单词经过Trie路径的长度是O(L)，每个节点只需要存下标，没有枚举组合的过程，总存储量是O(N * L)，而不是O(N * L^2)。当单词较长时，差别会非常明显。

2.4 方案对比速查

我个人推荐双Trie方案。它不但在复杂度上均衡，而且代码量完全可控，面试时还能展开聊Trie树的原理，比甩一个HashMap出来有含金量得多。

3. 双Trie树核心实现：从节点设计到查询逻辑

3.1 Trie节点的设计：关键不是“叶子标记”而是“路径索引”

很多看过Trie模板的人，写出来的节点是带一个boolean isEnd标志位的，用来标记一个单词是否在这里结束。但这道题的节点不能只存isEnd，因为我们要支持的是“以这个路径为前缀的所有单词”，而不是“路径恰好等于某个单词”。

比如查询前缀"ap"，"ap"本身可能不是单词，但它下面的"apple"、"applause"都算匹配。所以每个节点要额外维护一个List<Integer> indices，凡是插入过程中经过这个节点的单词，都把当前下标塞进列表里。

class TrieNode { TrieNode[] children = new TrieNode[26]; List<Integer> indices = new ArrayList<>(); }

children用长度26的数组，是因为题目明确输入只有小写字母。如果字符范围再大一些，可以换成HashMap<Character, TrieNode>，道理是一样的。

3.2 正序Trie和反序Trie的构建过程

构造函数里遍历words数组，对每个单词做两次插入：

public WordFilter(String[] words) { for (int i = 0; i < words.length; i++) { String w = words[i]; insert(prefRoot, w, i); insert(suffRoot, new StringBuilder(w).reverse().toString(), i); } }

insert方法要注意一个细节：根节点也要存下标。因为当pref或suff为空字符串时，空前缀匹配所有单词，空后缀也匹配所有单词，这个时候查询应该返回“全部单词下标列表”，正好对应根节点的列表。如果只存路径中的节点，空串就会返回错误结果。

private void insert(TrieNode root, String s, int idx) { TrieNode cur = root; cur.indices.add(idx); for (char c : s.toCharArray()) { int v = c - 'a'; if (cur.children[v] == null) { cur.children[v] = new TrieNode(); } cur = cur.children[v]; cur.indices.add(idx); } }

因为插入时idx是从0递增的，所以每个节点的indices列表天然保持升序。这个有序性在后面归并找最大值时非常关键。

3.3 f方法的查询逻辑：两个有序列表从尾部归并

查询分三步：

1. 在正序Trie中根据pref找路径，路径不存在直接返回-1。
2. 把suff反转，在反序Trie中找路径，路径不存在直接返回-1。
3. 拿到两个升序列表，用双指针从尾部开始找第一个相等的元素。

为什么从尾部？因为升序列表的尾部就是最大下标，题目要求返回最大下标，所以从尾部开始找，第一个相等的元素就是答案。

public int f(String pref, String suff) { List<Integer> prefixList = find(prefRoot, pref); if (prefixList == null) return -1; String reversedSuff = new StringBuilder(suff).reverse().toString(); List<Integer> suffixList = find(suffRoot, reversedSuff); if (suffixList == null) return -1; int i = prefixList.size() - 1; int j = suffixList.size() - 1; while (i >= 0 && j >= 0) { int a = prefixList.get(i); int b = suffixList.get(j); if (a == b) return a; if (a > b) { i--; } else { j--; } } return -1; }

这段双指针归并的逻辑，我单独解释一下为什么a > b时是让i--而不是j--。当前指针在A列表指向a，在B列表指向b。B列表从尾部往前的元素是递减的，而b是B列表当前剩下的最大元素，既然a > b，那说明A列表里这个a不可能出现在B列表里，因为B里最大的都够不到a，所以只能把A的指针前移。反过来同理。

find方法本身很简单，就是普通的Trie路径查找：

private List<Integer> find(TrieNode root, String s) { TrieNode cur = root; for (char c : s.toCharArray()) { int v = c - 'a'; if (cur.children[v] == null) { return null; } cur = cur.children[v]; } return cur.indices; }

这里对空字符串也自然成立：for循环一次都不走，直接返回根节点的indices。

3.4 复杂度分析：构建和查询分别花在哪

构建阶段的时间复杂度是O(N * L)。每个单词长度为L，要同时插入正序和反序两棵Trie，每棵树走L层，每层都做一次add操作，所以总的节点访问次数是2 * N * (L + 1)，忽略常数就是O(N * L)。

空间复杂度同样是O(N * L)。每个单词在每棵Trie中都会出现在路径上每个节点的indices里，路径长度约L，所以空间占用是O(N * L)。虽然看上去每个节点都存列表，但由于单词之间会共享前缀，实际存储量比最坏情况要小。

查询阶段的复杂度分两部分：找路径需要O(|pref| + |suff|)，归并列表需要O(|A| + |B|)，其中A和B分别是匹配前缀和后缀的下标集合大小。最坏情况下，如果pref是空串、suff也是空串，两个列表都是全量下标，归并就会扫描O(N)，但这种极端情况反而说明查询条件本身退化了，属于合理开销。

3.5 一个能加快归并的小优化

如果两个列表都很大，双指针归并要扫描较长的那条。实际测试中，可以提前把较小的列表转成HashSet，然后从较大的列表尾部往前遍历，第一个在HashSet中出现过的就是答案。这样时间复杂度能从O(|A| + |B|)降到O(min(|A|, |B|))，代价是多花一点构建HashSet的临时空间。

Set<Integer> set = new HashSet<>(suffixList); for (int i = prefixList.size() - 1; i >= 0; i--) { if (set.contains(prefixList.get(i))) { return prefixList.get(i); } }

注意这个优化在极端场景下收益明显，比如一个列表10000个元素，另一个只有10个元素，前者需要全部扫描，后者转成Set后只需要遍历大列表的前面几千个可能就命中了。不过双指针版本本身也够用，这个优化更像是“锦上添花”，面试时提一嘴能加分，但别为了优化把代码写复杂。

4. 完整Java实现与实测记录

4.1 可运行的完整代码

我把完整的WordFilter类写出来，加上详细的注释，方便直接对照。这里不整花活，就是最常规的双Trie实现：

import java.util.ArrayList; import java.util.List; class WordFilter { private TrieNode prefRoot = new TrieNode(); private TrieNode suffRoot = new TrieNode(); public WordFilter(String[] words) { for (int i = 0; i < words.length; i++) { String w = words[i]; insert(prefRoot, w, i); insert(suffRoot, new StringBuilder(w).reverse().toString(), i); } } public int f(String pref, String suff) { List<Integer> prefixList = find(prefRoot, pref); if (prefixList == null) return -1; String reversedSuff = new StringBuilder(suff).reverse().toString(); List<Integer> suffixList = find(suffRoot, reversedSuff); if (suffixList == null) return -1; int i = prefixList.size() - 1; int j = suffixList.size() - 1; while (i >= 0 && j >= 0) { int a = prefixList.get(i); int b = suffixList.get(j); if (a == b) return a; if (a > b) i--; else j--; } return -1; } private void insert(TrieNode root, String s, int idx) { TrieNode cur = root; cur.indices.add(idx); for (char c : s.toCharArray()) { int v = c - 'a'; if (cur.children[v] == null) { cur.children[v] = new TrieNode(); } cur = cur.children[v]; cur.indices.add(idx); } } private List<Integer> find(TrieNode root, String s) { TrieNode cur = root; for (char c : s.toCharArray()) { int v = c - 'a'; if (cur.children[v] == null) { return null; } cur = cur.children[v]; } return cur.indices; } static class TrieNode { TrieNode[] children = new TrieNode[26]; List<Integer> indices = new ArrayList<>(); } }

这段代码我实际提交通过过。需要注意的点是TrieNode的内部数组默认全是null，插入时判断子节点是否存在再新建，这个模式是Trie的通用写法。

4.2 用几个典型用例验证

下面这些用例基本覆盖了主要边界：

• words = ["apple"]，f("a", "e")返回0。正序Trie路径到a的列表是[0]，反序Trie路径到反转后的e（也就是字符串"e"）的列表是[0]，归并命中0。
• words = ["apple", "applause"]，f("app", "e")返回1。因为两个单词都以"app"开头、以"e"结尾，返回大下标1。
• words = ["apple", "apple"]，f("a", "e")返回1。重复单词不算错，只要正确处理下标即可。插入时会分别在[0]和[1]两个位置各插一次，两个列表都包含0和1，归并从尾部找到1。
• words = ["apple"]，f("", "")返回0。两个空串都对应根节点列表，归并直接命中。
• words = ["apple"]，f("b", "e")返回-1。正序Trie路径走到b时发现子节点不存在，提前返回-1。

我实际调试时发现，最容易出错的反而不是这些复杂逻辑，而是new StringBuilder(suff).reverse().toString()写成了new StringBuilder(suff)，导致后缀查询一直走错路径。所以构建反序Trie和查询反序Trie时，一定要保证两处的反转逻辑一致。

4.3 实际遇到过的性能问题

第一次提交双Trie版本时，我以为空间没问题，结果某个用例直接内存爆掉。排查后发现是ArrayList扩容问题：每个节点默认初始容量是10，但某些热门前缀节点下会积累几千个下标，频繁扩容会浪费大量空间和时间。

解决方法是预估容量。因为words的个数在构造函数里是已知的，可以在TrieNode初始化时直接指定一个较大的初始容量，或者等插入完成后把ArrayList转换成刚好容量的数组保存。后者更节省内存，但代码复杂度会上升。实际做题时，我最常用的折中手段是把indices在插入前就预估容量为words.length / 2，这样大部分节点扩容次数明显减少。

4.4 一个小技巧：复用同一套insert和find

正序和反序Trie共用了同一套insert和find方法，只是传入的root和字符串不同。这样做代码更干净。如果非要写两套Trie类结构，代码会成倍膨胀，而且容易在一个地方改了另一个地方忘改。我建议就保持一个TrieNode类，两个不同的根节点实例，逻辑上天然隔离。

5. 常见问题与排查速查

5.1 查询结果总是不对，缺了符合条件的单词

排查思路：检查插入逻辑，确认每个节点都存了当前下标，而不只是叶节点存。很多人写Trie时习惯在单词结束时标记isEnd，随手就只在这个位置add下标。对于f("ap", "e")这种查询，正序Trie走到ap节点时，如果ap不是单词结尾，就可能拿不到任何东西。记住，这道题里节点的作用是“路径索引”，不是“单词终止标记”。

还有另一个迷之错误：f方法里忘了反转suff，直接拿suff去反序Trie里查询。反序Trie里存的都是反转后的单词路径，拿正序后缀去查，大概率查不到。

5.2 返回的不是最大下标

如果归并双指针是从列表头部开始遍历的，找到的第一个相等值是最小下标，不是最大下标。要返回最大下标，要么从尾部开始，要么把indices列表存成降序。从尾部开始更简单，因为插入顺序天然就是升序，不用额外处理。

还有一种情况：你以为返回的ans会不断覆盖成最大值，但代码里一旦找到相等就立刻返回了，中间命中的恰好不是最大交集。所以别贪图省事跳过归并逻辑，老老实实处理两个有序列表的交集。

5.3 空字符串问题：直接漏掉根节点

pref或suff是空串时，命中根节点列表是正确行为。但很多人在find方法里写了类似“如果路径不存在就返回一个特殊值”的逻辑，或者在处理空字符串时单独返回null，结果查询f("", "")变成-1。正确做法是让find对空串自然走完for循环，返回根节点的indices。

这里我也遇到过一版代码，为了优化查询速度，给空串增加了一个if (s.isEmpty()) return singleNode.indices;的短路逻辑，但因为忘了给根节点放索引，短路返回了个空列表，排查了很久。这个细节千万别漏。

5.4 内存爆炸或时间超限

常见原因有以下几类：

• 用了HashMap预计算方案，单词长度一大就崩。换成双Trie。
• 用了双Trie但ArrayList扩容太频繁。参考4.3里的做法，预分配容量或转成数组。
• 归并时可以选较小列表转HashSet，减少大列表全量扫描。
• 如果节点数组的稀疏度很高，可以把TrieNode[] children换成HashMap<Character, TrieNode>，空间更灵活，但速度略慢。真实数据分布较均匀的情况下，数组方案更稳。

5.5 速查表

6. 从这道题延伸出去：多条件检索的通用套路

6.1 变体一：统计满足条件的单词数量

如果把返回值从“最大下标”改成“满足条件的单词个数”，该怎么办？答案还是老朋友——两个有序列表求交集长度。双指针从头部开始，遇到相等时计数并同时移动两个指针，遇到不相等时移动较小值那侧。这一步其实就是标准的有序集合求交集模板。LeetCode 745考的是“交集的最大值”，去掉“最大值”限制后就是“交集的大小”，换个帽子又是另一道题。

6.2 变体二：支持动态插入单词

Trie方案天然支持动态插入，随时可以insert一个新单词，路径上所有节点更新即可。HashMap预计算方案虽然也能追加key，但新单词引入的前缀后缀组合会让表越滚越大，动态场景下劣势非常明显。所以如果你遇到一个支持动态添加单词的变体题，双Trie基本是唯一合理选择。

6.3 变体三：多字段联合检索和搜索引擎的倒排索引

这道题的底层思想，本质上和搜索引擎里的倒排索引一致。倒排索引里，每个关键词背后都挂着一个有序的文档ID列表，查询“关键词A且关键词B”时，就是对两个有序列表求交集。我很久以前看搜索引擎原理时没想通为什么倒排索引查询能这么快，刷了这道题才真正体会到“有序列表归并”的威力。

实际工程里可能比这复杂得多，比如要处理跳表、位图压缩、近似归并等，但核心还是“多个有序列表求交集”这一套。面试时如果能把LeetCode 745和倒排索引联系起来，会让面试官觉得你不只是会背题，而是真的理解了数据结构的应用场景。

6.4 面试官追问的常规问答

如果你在面试中写了双Trie方案，大概率会被追问这几个问题：

问：为什么用双Trie，而不是把“后缀+#+前缀”整体塞进一棵Trie？

答：整体塞进去的构建复杂度是O(N * L^2)，因为每个单词要枚举所有后缀和前缀组合。双Trie每条路径只存O(L)个节点，空间和时间都更可控。

问：如果输入不只是26个小写字母，有什么影响？

答：把children数组换成HashMap，其余逻辑不变。Trie的结构本身不依赖固定字符集，只是数组实现更高效。

问：如果单词特别长，最坏情况会怎样？

答：空间复杂度还是O(N * L)，但常数变大。如果单词全都不共享前缀，Trie接近链表形态，空间利用率变低，这时候可以考虑压缩Trie或者用后缀数组做预处理。

我个人在实际操作中的体会是，这道题的代码并不难，难的是把“两个列表有序归并”这个思路讲清楚。刷题的时候不要只满足于提交通过，试着在注释里写下每个节点为什么存indices、归并为什么从尾部开始，这样过半个月回头看还能快速捡起来。

最后再分享一个小技巧：如果你像我一样经常在Trie题目里绕晕，可以准备一张几行的模板代码，把insert和find这种通用方法固定下来，遇到变形题目时先套模板，再针对题目改节点字段。LeetCode 745就是一个典型的“模板+自定义字段”的题目，把前缀树模板和有序列表归并结合起来，很多自媒体题解里的“花式写法”反而没有这种基础组合来得可靠。