刷算法题刷到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预计算、双Trie2.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预计算思路简单但空间容易炸这种方案的脑洞是我能不能把所有可能被查询的“后缀 分隔符 前缀”组合直接存成哈希表的keyvalue就是对应单词的下标查询时拼好key直接查表时间复杂度甚至能到O(1)。代码看起来会非常短class WordFilter { MapString, 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会出现歧义。比如prefab、suffc拼出来是cab下次查询prefab、suffca拼出来还是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 方案对比速查方案构建复杂度查询复杂度空间复杂度适用场景暴力扫描O(1)O(N * L)O(1)小数据量、确认题意HashMap预计算O(N * L^2)O(L)O(N * L^2)单词短、数量少双TrieO(N * L)O(L |A| |B|)O(N * L)通用面试首选我个人推荐双Trie方案。它不但在复杂度上均衡而且代码量完全可控面试时还能展开聊Trie树的原理比甩一个HashMap出来有含金量得多。3. 双Trie树核心实现从节点设计到查询逻辑3.1 Trie节点的设计关键不是“叶子标记”而是“路径索引”很多看过Trie模板的人写出来的节点是带一个boolean isEnd标志位的用来标记一个单词是否在这里结束。但这道题的节点不能只存isEnd因为我们要支持的是“以这个路径为前缀的所有单词”而不是“路径恰好等于某个单词”。比如查询前缀apap本身可能不是单词但它下面的apple、applause都算匹配。所以每个节点要额外维护一个ListInteger indices凡是插入过程中经过这个节点的单词都把当前下标塞进列表里。class TrieNode { TrieNode[] children new TrieNode[26]; ListInteger indices new ArrayList(); }children用长度26的数组是因为题目明确输入只有小写字母。如果字符范围再大一些可以换成HashMapCharacter, 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方法的查询逻辑两个有序列表从尾部归并查询分三步在正序Trie中根据pref找路径路径不存在直接返回-1。把suff反转在反序Trie中找路径路径不存在直接返回-1。拿到两个升序列表用双指针从尾部开始找第一个相等的元素。为什么从尾部因为升序列表的尾部就是最大下标题目要求返回最大下标所以从尾部开始找第一个相等的元素就是答案。public int f(String pref, String suff) { ListInteger prefixList find(prefRoot, pref); if (prefixList null) return -1; String reversedSuff new StringBuilder(suff).reverse().toString(); ListInteger 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 ListInteger 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的临时空间。SetInteger 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) { ListInteger prefixList find(prefRoot, pref); if (prefixList null) return -1; String reversedSuff new StringBuilder(suff).reverse().toString(); ListInteger 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 ListInteger 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]; ListInteger 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换成HashMapCharacter, TrieNode空间更灵活但速度略慢。真实数据分布较均匀的情况下数组方案更稳。5.5 速查表症状可能原因解决办法一个匹配单词都查不到只在叶子节点存下标所有经过节点都要add后缀条件一直错没反转suff就去反序Trie查查询和构建时都保持反转结果不是最大下标双指针从头部开始从尾部开始归并空串查询返回-1根节点没存全量下标插入时在根节点add内存爆掉HashMap组合爆炸 / ArrayList扩容过多换双Trie / 预分配容量超时归并扫描了整个大列表小列表转HashSet再遍历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就是一个典型的“模板自定义字段”的题目把前缀树模板和有序列表归并结合起来很多自媒体题解里的“花式写法”反而没有这种基础组合来得可靠。