前几天在刷题群里看到有人问 LeetCode 745,说f(pref, suff)这个方法死活想不明白。我点进去看了一眼,脑子里第一反应是:这题表面考字符串匹配,实际上是在考你对 Trie 树的理解深度。前缀匹配很多人都写过,后缀匹配也不算难,但把两个条件同时压在一棵树上、还要保持高效查询,就一下子把难度拉上去了。这篇文章我打算从暴力解法一路拆到最优解,把每一步的思路、取舍、坑位都讲清楚,适合刚学完 Trie 想进阶的读者,也适合面试前拿这题临时抱佛脚的朋友。
1. 先吃透题目:它到底在问什么
1.1 题面拆解与示例推演
LeetCode 745 的题面不算长,核心是让你设计一个WordFilter类,构造函数接收一个字符串数组words,然后实现一个方法f(String pref, String suff),返回所有同时满足两个条件的单词下标:这个单词必须以pref开头,并且以suff结尾。如果有多个单词满足条件,返回下标最大的那个;如果没有,返回-1。
举个例子,words = ["apple", "app", "application", "ape"],这时候调用f("app", "le"):
"apple"以"app"开头、以"le"结尾,下标 0 满足;"app"以"app"开头,但结尾是"pp",不满足;"application"以"app"开头,但结尾是"on",不满足;"ape"不以"app"开头,不满足。
所以返回0。如果words里再出现一个"apple"放在下标 3 的位置,那答案就变成3,这就是"返回最大下标"的含义。
这个逻辑本身不复杂,甚至第一版暴力代码十分钟就能写完。但题目给了一个隐形的约束:words的长度和单次查询量都可能很大。如果你的f方法每次都要遍历整个数组、做两次字符串匹配,极端情况下性能会非常难看。这也是为什么这题会被标记为难度的原因——它考的不是你会不会调startsWith和endsWith,而是你能不能针对"前缀 + 后缀"这个组合条件,设计一套预处理方案,把查询时间压下来。
1.2 为什么说它是 Trie 树的进阶应用题
如果你只做过 LeetCode 208(实现 Trie)或者 211(添加与搜索单词),你可能会觉得 Trie 树就是个"查前缀"的工具。745 这题最狠的地方在于,后缀这个条件是反着来的:后缀"le"在单词尾部,而 Trie 树天然是从头到尾构建的,按正常顺序插入单词,根本没法直接查后缀。
这时候就有几条路可以走:
- 只对前缀建 Trie,后缀靠遍历候选列表硬扛;
- 建两棵 Trie,一棵正序处理前缀,一棵倒序处理后缀,查询时求交集;
- 把后缀和前缀拼成一个复合键,插入同一棵 Trie,查询时一次走到底。
这三条路对应的时间复杂度、空间复杂度、代码复杂度都不一样,也是这篇文章的主体内容。我个人强烈建议你先不要看题解,自己把这三条路都写一遍。原因很简单:这类"多个条件组合查询"的题目,思路上的核心解法都是相通的。你在这题里想明白的"复合键拼接"技巧,后面遇到"过滤词过滤""双条件查找"之类的场景还能继续复用。
2. 第一版解法:暴力匹配,先保证正确
2.1 暴力思路与代码
遇到这种题,先别急着想优化,把暴力解法写出来能帮你确认对题目的理解没有偏差。暴力解法的思路非常直白:每次调用f的时候,从数组末尾往前遍历,逐个检查单词是否满足两个条件,第一个命中的就是最大下标。
class WordFilter { private String[] words; public WordFilter(String[] words) { this.words = words; } public int f(String pref, String suff) { for (int i = words.length - 1; i >= 0; i--) { String w = words[i]; if (w.startsWith(pref) && w.endsWith(suff)) { return i; } } return -1; } }注意这里有个小技巧:从数组尾部往前遍历,而不是从头往后遍历再维护一个max变量。这样写少一个比较运算,语义也更直接——你要的是最大下标,而最大下标天然出现在数组靠后的位置。
startsWith和endsWith是 Java 字符串类自带的方法,内部实现是字符数组的逐位比较。对一个长度为 L 的单词,前缀匹配的耗时是O(len(pref)),后缀匹配的耗时是O(len(suff)),而pref和suff的长度加起来最多不超过 L,所以单次判断的耗时可以看作O(L)。
2.2 复杂度分析和它的问题在哪
构造阶段没有做任何预处理,时间复杂度是O(1)。查询阶段最坏要遍历整个数组,每次调用f的复杂度是O(N * L),其中 N 是数组长度,L 是单词平均长度。
这个复杂度在数据量小的时候完全没问题,我用本地的几百个单词测试,肉眼几乎感觉不到延迟。但题目不会让你这么舒服:words长度可以达到上万,查询次数也可以上万,O(N * L)的查询复杂度一乘就是亿级别的字符比较,超时是必然的。
我之前见过一种写法,是先把所有满足条件的下标收集到一个List里,最后取最大值。这个思路本身没错,但完全是多此一举,因为从尾部开始遍历就自然拿到了最大值。写代码的时候一定要想清楚一个原则:能一次遍历解决的事情不要拆成两次。
暴力解法不是用来交的,它是用来当基准测试的。后面你写出 Trie 解法之后,可以随机生成一批数据,拿暴力和 Trie 解法的结果对拍,能帮你快速确认 Trie 实现没有逻辑错误。这个习惯我后面还会强调。
3. 前缀 Trie + 后缀检查:最常见的折中方案
3.1 设计思路:让 Trie 帮你缩小候选集
暴力的痛点在于,每次查询都要扫描全部 N 个单词。那能不能只扫描一部分?前缀 Trie 的思路就是把"以pref开头"这个条件从"遍历所有单词"变成"直接定位到前缀对应的节点",然后只检查这一小批候选单词的后缀。
举个例子,words里有 10000 个单词,但以"app"开头的只有 3 个。用前缀 Trie 定位到"app"对应的节点后,只需检查这 3 个单词的后缀,查询速度直接快了几个数量级。
实现上有两个关键点:
- 每个节点需要额外存一个索引列表,记录"经过这个节点的所有单词的下标";
- 查询时先顺着
pref的字符走到目标节点,再遍历这个节点上的索引列表,用endsWith过滤后缀。
为什么要在节点上挂索引列表?因为 Trie 节点本身只承担字符串匹配的功能,它不知道哪些单词经过了自己。只有把下标信息附加在节点上,查询时才能快速拿到候选集合。
3.2 建树细节:节点上挂索引列表
class WordFilter { class TrieNode { TrieNode[] next = new TrieNode[26]; List<Integer> indices = new ArrayList<>(); TrieNode() {} } private TrieNode root; private String[] words; public WordFilter(String[] words) { this.words = words; root = new TrieNode(); for (int i = 0; i < words.length; i++) { TrieNode node = root; for (char c : words[i].toCharArray()) { if (node.next[c - 'a'] == null) { node.next[c - 'a'] = new TrieNode(); } node = node.next[c - 'a']; node.indices.add(i); } } } public int f(String pref, String suff) { TrieNode node = root; for (char c : pref.toCharArray()) { if (node.next[c - 'a'] == null) { return -1; } node = node.next[c - 'a']; } List<Integer> candidates = node.indices; for (int i = candidates.size() - 1; i >= 0; i--) { int idx = candidates.get(i); if (words[idx].endsWith(suff)) { return idx; } } return -1; } }有一个细节很多第一次写的人会漏:indices列表在插入的时候,i是从 0 递增的,所以列表里的下标天然是升序的。查询时从列表尾部往前遍历,就能优先检查下标更大的单词,一旦命中就返回,不用再比较大小。
这个方案的好处是代码逻辑直白,建树过程跟普通 Trie 几乎没有区别,只是多了个列表维护的操作。坏处也很明显:如果pref是空字符串,前缀 Trie 会退化成直接检查所有单词,和暴力解法没有本质区别。
3.3 查询流程与复杂度分析
假设单词数量为 N,单词平均长度为 L,候选集合大小为 M。
- 构建:每个单词的每个字符都要走一次 Trie,每次走到节点都要往列表里加一个下标。构建复杂度是
O(N * L)。 - 查询:需要走
len(pref)步找到目标节点,然后遍历候选集合做endsWith判断。前缀匹配的部分是O(len(pref)),后缀检查的部分是O(M * L)。
最坏情况下,pref是空串,所有单词都是候选,M等于 N,查询复杂度退化成O(N * L),和暴力解法一样。所以在实际使用中,这个方案适合"前缀区分度高"的数据场景,比如单词表里前缀分布非常分散,pref能快速过滤掉大部分单词。
我第一次写这题用的就是这个方案,因为思路好想,代码也不容易出错。但如果你追求性能上限,尤其是前缀很可能为空串的场景,这个方案就不够看了。
4. 双 Trie 求交集:思路直观但代价不小
4.1 正反两棵树的设计
前缀 Trie 的瓶颈在于,后缀过滤靠的是"遍历候选列表 + 逐词检查",候选列表一旦很大就白搭。那能不能把后缀也做成 Trie,让两个条件都通过"快速定位"来完成?
答案是可以,思路是建两棵树:一棵正序 Trie 处理前缀,一棵倒序 Trie 处理后缀。查询的时候,先从前缀 Trie 取出所有以pref开头的单词下标集合 A,再从后缀 Trie 取出所有以suff结尾的单词下标集合 B,然后求 A 和 B 的交集中的最大值。
为什么后缀树要倒序插入?因为 Trie 只能从头匹配。后缀匹配的本质是"以suff结尾",把单词反转一下,后缀就变成了反转后字符串的前缀。比如"apple"要匹配后缀"le",反转成"elppa","le"反转成"el",问题就变成了判断"el"是否是"elppa"的前缀。
4.2 双指针求最大交集
两个集合都是升序排列的下标列表,求最大交集不需要嵌套循环,用双指针从尾部往头部扫就行:
int i = listA.size() - 1; int j = listB.size() - 1; while (i >= 0 && j >= 0) { int a = listA.get(i); int b = listB.get(j); if (a == b) { return a; } else if (a > b) { i--; } else { j--; } } return -1;这段逻辑的原理是:两个有序数组找交集,从尾部开始比较,谁大谁往左移。每次比较都让其中一个指针移动,复杂度是O(|A| + |B|),比|A| * |B|的嵌套循环好得多。
4.3 为什么实际效果一般
这个方案理论上是通的,但有几个问题:
- 空间翻倍。你需要维护两棵完整的 Trie,每个节点都要挂索引列表,内存开销比单棵树大。
- 建树时间翻倍。每个单词要被插入两次,正序一次、倒序一次。
- 查询时交集大小不可控。当
pref或suff是空串时,对应的集合 A 或 B 会包含所有单词,双指针的复杂度退化为O(N)。
更重要的是,代码量明显增加。你需要两个insert流程、两个search流程,还要处理空串时的边界逻辑。相比下一节要讲的复合键方案,双 Trie 属于"思路正确但性价比不高"的选择。我在面试模拟中写过一次这个方案,写完就想拍大腿:同样两个字符集合并成一个复合键,所有麻烦事都省了。
5. 复合键 Trie:这道题的经典最优解
5.1 一个容易被忽略的细节:分隔符
双 Trie 的痛点是两个集合求交集,那能不能让"前缀 + 后缀"成为一个整体,直接塞进一棵 Trie?
可以。核心技巧是把单词的所有可能后缀,分别和完整单词拼接成一个复合键,插入 Trie。比如单词"apple":
- 后缀
""拼上"apple",得到"{apple" - 后缀
"e"拼上"apple",得到"e{apple" - 后缀
"le"拼上"apple",得到"le{apple" - 后缀
"ple"拼上"apple",得到"ple{apple" - 后缀
"pple"拼上"apple",得到"pple{apple" - 后缀
"apple"拼上"apple",得到"apple{apple"
查询的时候,把suff + "{" + pref拼起来,直接走一次 Trie。能走到终点节点,就说明存在某个单词同时满足两个条件,终点节点上存的最大下标就是答案。
这里的{是关键。它不能随便选,必须满足一个条件:不可能是单词本身包含的字符。题目限定单词和查询字符串只包含小写英文字母,那就用{,因为它的 ASCII 码是 123,比z(122)大 1,不会被误认为是路径中的普通字符。
为什么要刻意强调这一点?因为如果分隔符选了一个也出现在单词里的字符,路径就会产生歧义。比如用a做分隔符,单词"aba"拼出来的复合键"a{aba"和某个其他单词的复合键路径就可能混淆,导致查询结果错误。
5.2 建树过程:每个后缀都要和完整单词绑定
建树时,外层循环遍历每个单词,内层循环枚举单词的所有后缀位置,构造复合键并插入。
class WordFilter { class TrieNode { TrieNode[] next = new TrieNode[27]; int maxIndex = -1; TrieNode() {} } private TrieNode root; public WordFilter(String[] words) { root = new TrieNode(); for (int i = 0; i < words.length; i++) { String w = words[i]; // 枚举后缀起始位置,从空后缀开始 for (int j = 0; j <= w.length(); j++) { String key = w.substring(j) + '{' + w; insert(key, i); } } } private void insert(String s, int idx) { TrieNode node = root; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int pos = (c == '{') ? 26 : (c - 'a'); if (node.next[pos] == null) { node.next[pos] = new TrieNode(); } node = node.next[pos]; // 因为插入的 idx 天然递增,直接覆盖即可 node.maxIndex = idx; } } public int f(String pref, String suff) { String key = suff + '{' + pref; TrieNode node = root; for (int i = 0; i < key.length(); i++) { char c = key.charAt(i); int pos = (c == '{') ? 26 : (c - 'a'); if (node.next[pos] == null) { return -1; } node = node.next[pos]; } return node.maxIndex; } }这里有一个细节值得单独拿出来说:insert里为什么直接node.maxIndex = idx,而不是Math.max(node.maxIndex, idx)?
因为建树的i是从 0 到words.length - 1递增的,越靠后的单词下标越大。当同一个节点被多次访问时,最后一次访问一定来自下标最大的单词。所以直接覆盖赋值,天然就是最大值。这个思路跟暴力解法里"从尾部往前遍历"异曲同工——利用插入顺序,少写一堆比较逻辑。
5.3 查询过程:一次路径匹配直接出结果
查询时把suff + '{' + pref拼起来,顺着 Trie 往下走:
- 如果中途某个节点不存在,说明没有任何单词同时满足两个条件,返回
-1; - 如果顺利走到终点,终点节点的
maxIndex就是答案。
以words = ["apple", "app", "application"]为例,查询f("app", "le"):
- 拼出来的 key 是
"le{app"; - 走
l->e->{->a->p->p,终点节点就是复合键"le{app"对应的节点; - 这个节点上存的最大下标来自单词
"apple",也就是 0,返回 0。
整个过程没有遍历任何候选列表,没有调用endsWith,时间复杂度完全取决于 key 的长度。
5.4 完整复杂度分析与适用场景
- 构建:每个单词长度为 L,有 L + 1 种后缀(包括空后缀),每个复合键的长度约为
L + 1 + L = 2L + 1,所以每个单词的插入耗时是O(L^2),整体构建复杂度是O(N * L^2)。 - 查询:key 的长度是
len(suff) + 1 + len(pref),所以查询复杂度是O(len(pref) + len(suff))。这个复杂度与数组长度 N 完全无关,这是它最大的优势。 - 空间:每个复合键的每个字符都是一个节点,空间复杂度同样是
O(N * L^2)。不过考虑到题目限制单词长度通常不超过 10,L^2这个因子完全在可接受范围内。
我第一次分析到这里的时候有点犹豫,觉得O(N * L^2)的构建时间会不会太夸张。后来算了一下具体数字:假设 N = 15000,L = 10,构建操作大概是 15000 * 100 = 150 万次字符插入,对现代计算机来说是毫秒级的操作,完全不用纠结。
所以这个方案最适合的场景就是"查询次数多、单词长度短"。LeetCode 745 的数据条件恰好符合这个特征,这就是它成为经典最优解的原因。
6. 哈希表方案:更直白的空间换时间
6.1 前缀表 + 后缀表的设计
如果你对 Trie 的节点操作不太熟,其实还有一条路:用两个哈希表,一个存所有可能前缀对应的下标列表,一个存所有可能后缀对应的下标列表。查询的时候,从两个表分别取出候选集合,再求交集。
class WordFilter { private Map<String, List<Integer>> prefixMap = new HashMap<>(); private Map<String, List<Integer>> suffixMap = new HashMap<>(); public WordFilter(String[] words) { for (int i = 0; i < words.length; i++) { String w = words[i]; for (int j = 0; j <= w.length(); j++) { String pre = w.substring(0, j); String suf = w.substring(j); prefixMap.computeIfAbsent(pre, k -> new ArrayList<>()).add(i); suffixMap.computeIfAbsent(suf, k -> new ArrayList<>()).add(i); } } } public int f(String pref, String suff) { List<Integer> a = prefixMap.getOrDefault(pref, Collections.emptyList()); List<Integer> b = suffixMap.getOrDefault(suff, Collections.emptyList()); int i = a.size() - 1; int j = b.size() - 1; while (i >= 0 && j >= 0) { int x = a.get(i); int y = b.get(j); if (x == y) { return x; } else if (x > y) { i--; } else { j--; } } return -1; } }这个方案的代码比 Trie 方案短不少,理解门槛也低,因为哈希表是日常开发里最常用的数据结构。构建时枚举每个单词的所有前缀和后缀,分别存入两个 Map;查询时直接get两个列表,双指针求最大交集。
6.2 复杂度对比:和 Trie 方案谁更强
- 构建:每个单词长度 L,枚举前缀和后缀的总次数为
2 * (L + 1),每个子串都要插入哈希表。构建复杂度O(N * L),这里注意它其实比复合键 Trie 的O(N * L^2)更好一点。 - 查询:从两个 Map 取列表是
O(len(pref))和O(len(suff))(取决于 HashMap 的哈希计算和键比较),最耗时的部分还是双指针求交集,最坏情况是O(|A| + |B|)。 - 空间:两个 Map 各存约
N * L个键值对,每个值都是一个列表,空间开销同样是O(N * L)。
单从复杂度看,哈希表方案构建更快、代码更短、空间相当,那为什么在线评测中它不是主流答案?
因为整数溢出问题比较隐蔽。上述代码里我用prefixMap.getOrDefault(pref, Collections.emptyList())来处理不存在的键,但Collections.emptyList()返回的是一个泛型List<Object>,需要强转。如果你忘了处理泛型警告,编译期可能不报错,运行期直接抛ClassCastException。我见过好几个人的代码死在这个地方,找半天才发现是emptyList的泛型问题。
另一个问题是哈希表方案在面试中很难体现你的数据结构功底。面试官看到你用两个 HashMap 解这道题,多半会追问一句:如果pref和suff都很长,哈希表的开销会不会很大?HashMap 对所有长度的字符串都做hashCode计算和equals比较,长度大的键会比 Trie 逐字符查找慢得多。相比之下,复合键 Trie 的每次查找只需要做字符数组的下标跳转,常数因子小很多。
6.3 实战选型建议
说实话,如果只追求"能 AC",哈希表方案完全够用。但如果你是为了准备面试,我建议你把复合键 Trie 的写法背熟,因为面试官大概率会顺着这道题问你 Trie 的边界条件、分隔符处理、空间开销,这些都是哈希表方案里不存在的知识点。
拿我自己当例子,我用哈希表方案 AC 之后,随手把复合键 Trie 也写了一版。两版跑同一批测试数据,Trie 的查询时间大约是哈希表的 60% 左右。在数据量大的情况下,这个差距还会继续拉大。如果你的业务场景是"构建一次、查询海量次",那构建时间根本不是瓶颈,查询时间的常数因子反而至关重要。
7. 边界情况与典型坑位速查
7.1 空字符串的语义
pref或suff为空串,或者两者皆空,是这道题最常见的边界条件。空串是任何字符串的前缀,同时也是任何字符串的后缀。
- 复合键 Trie 里,如果
pref为空,查询 key 是suff + "{,路径终点就是所有以suff结尾的单词对应的最大下标; - 如果
suff为空,查询 key 是"{+ pref,路径终点是所有以pref开头的单词对应的最大下标; - 两者皆空,查询 key 是
"{",终点是全部单词的最大下标。
写代码时你会发现一个很有意思的现象:复合键 Trie 处理空串根本不需要额外判断,因为substring(j)和substring(0, j)在j = 0时天然产生空串,路径照常走。而哈希表方案在空串场景下则需要额外注意,因为substring(0, 0)生成的是空字符串,这个空串作为 key 是合法的,但如果 Map 里没存,getOrDefault会返回空列表,最终结果正确但依赖边界数据。
7.2 重复单词与索引覆盖
words里可能存在完全相同的单词,比如["apple", "banana", "apple"]。这时下标 0 和 2 都对应单词"apple",查询f("app", "le")应该返回 2。
复合键 Trie 的做法:插入第二个"apple"时,路径上所有节点的maxIndex会被覆盖为 2,查询结果自然正确。哈希表方案的做法:两个列表里都包含 0 和 2,双指针从上往下找交集时,会先匹配到 2。所以两种方案都不需要额外处理重复单词,前提是你的插入逻辑按我说的方式实现了。
如果你在节点上存的是List<Integer>而不是maxIndex,那重复单词也不会出问题,因为列表里会同时存 0 和 2,查询时从尾部扫描即可。唯一的差别是空间和常数因子,存maxIndex明显更优。
7.3 几个容易写错的细节
第一,f方法参数顺序是pref在前、suff在后。我见过有人把这两者搞反,结果怎么查都返回-1,排查半天才发现是参数顺序错了。
第二,复合键 Trie 的数组大小是 27 而不是 26。'{'映射到下标 26,如果你的数组初始化成 26,插入时node.next[26]会直接数组越界。这个错误在本地调试时很容易暴露,但在线上环境里可能被异常捕获吞掉。
第三,substring(j)的 j 范围是0 <= j <= w.length()。当j = w.length()时生成空后缀,这是合法的,因为空串也是后缀。漏掉这个边界会导致f(pref, "")的查询结果全部错误。
第四,不管用什么方案,查询结果的语义都是"满足条件的最大下标",不是"满足条件的下标个数"。这个返回值类型是int,找不到返回-1,很多人写习惯了下标从 0 开始,忘记-1这个约定。
7.4 常见问题速查表
我把实战中容易踩的坑整理成一个表格,方便你排查问题的时候对照。
| 问题现象 | 可能原因 | 排查方向 |
|---|---|---|
| 查询总是返回 -1 | 参数顺序写反 | 检查调用f(pref, suff)时两个参数是否对应正确 |
| 空后缀查询结果错误 | substring循环漏掉j == w.length() | 确认内层循环是j <= w.length() |
| 插入复合键时数组越界 | Trie 节点数组大小是 26 | 改成 27,'{'映射到下标 26 |
| 结果比预期小 | 节点存的是最小下标而非最大 | 确认插入时maxIndex是否被递增顺序覆盖 |
| HashMap 方案强转异常 | Collections.emptyList()泛型不匹配 | 显式写成Collections.<Integer>emptyList() |
8. 四种方案放一起:怎么选、怎么用
8.1 复杂度总览
把四种方案的复杂度整理成一张表,方便面试时快速说出差异:
| 方案 | 构建复杂度 | 查询复杂度 | 空间复杂度 | 代码量 |
|---|---|---|---|---|
| 暴力遍历 | O(1) | O(N * L) | O(N * L) | 最少 |
| 前缀 Trie + 后缀检查 | O(N * L) | O(len(pref) + M * L) | O(N * L) | 较少 |
| 双 Trie 求交集 | O(N * L) | O(len(pref) + len(suff) + M) | O(N * L) | 最多 |
| 复合键 Trie | O(N * L^2) | O(len(pref) + len(suff)) | O(N * L^2) | 中等 |
| 哈希表双 Map | O(N * L) | O(len(pref) + len(suff) + M) | O(N * L) | 中等 |
这里的 M 代表候选集合大小。前缀 Trie 加后缀检查、双 Trie、哈希表三个方案在查询时都隐含着 M 这个因子,最坏情况会退化为 O(N)。只有复合键 Trie 的查询复杂度不依赖 N,是真正意义上的稳定快速。
8.2 面试中怎么答这道题
如果面试官让你现场写这道题,我建议按照这个节奏来:
先快速给出暴力解法,让面试官知道你理解了题面。然后主动指出暴力解法的性能瓶颈在每次全量扫描,引出"用空间换时间"的思路。接着写出前缀 Trie 加后缀检查的版本,这是最自然的过渡。最后,如果面试官追问"前缀为空串怎么办",再把复合键 Trie 的方案抛出,重点讲清楚分隔符{的选择理由。
这样的答题节奏有层次感,每一步的动机都很清晰,面试官能看出你不只是背了题解,而是真的理解每种方案的适用边界。
我个人在模拟面试中试过直接写复合键 Trie,结果被追问了很多细节。反而从朴素方案一步步往上推,面试体验更流畅,因为每一步优化都是"被逼"出来的,不是凭空跳出来的。
9. 写在最后:一个可以迁移的技巧
讲真,这道题最让我印象深刻的不是 Trie 本身,而是那个分隔符{。它把后缀匹配问题变成了前缀匹配问题,把两个条件的交集查询变成了一次路径查找。这个"拼接 + 分隔符"的技巧,在很多时候都能用上。
比如我之前处理过一个敏感词过滤的需求,需要同时匹配"开头词"和"结尾词",当时我第一反应就是建两棵 Trie 做交集,后来突然想起 745 这题的复合键思路,直接把开头结尾拼成一个带分隔符的键,代码量少了一半。再比如做搜索建议的时候,需要根据用户输入同时匹配品牌和型号,同样是两个条件,同样可以用复合键。
这题刷完,我建议你在本地把四种方案都写一遍,互相跑一下对拍。不要只看题解觉得"懂了",因为真正写起来你会发现,光是substring的边界条件、节点数组的大小、空串的处理,就有十几个容易出错的地方。等你全部踩过一遍,再回头看这道题,它的难度就会从 hard 降到 medium 以下。
如果你在写的过程中遇到某个具体问题卡住了,欢迎回来评论区留言,多一个人对照排查总是好的。