题目重点：把第一组全部前缀合进Trie，逐项返回第二组的最长匹配长度，区分公共前缀与完整单词匹配。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入为两个字符串数组，返回每个query与任一source字符串的最大公共前缀长度。
- 比较从字符串开头开始，区分大小写，按code point计长；如果元素是数字需先确认转字符串和负号规则。
- 空source对应所有答案零；空query答案零。若正式结果是全局最大值，可再对逐query结果取max。
解题路线
- 暴力逐query和每个source逐字符比较，复杂度随两数组乘积增长。Trie把source相同前缀存一次，让一次query只沿自己的字符向前走。
- 插入source时每读一字符走到对应子节点，没有则创建。这里只问公共前缀长度，不要求匹配结果恰好是source完整单词，因此无需终止标记也能求答案。
- query从root开始，首个不存在的字符边前停止。已经走过的深度等于最大公共前缀，因为那条路径至少由一个source插入；不存在下一条边说明没有source能匹配更长。
- source=[abcd,abx]，query=abcZ走到abc即停，答案3，即使abc不是完整source词也合法。若改成最长完整单词前缀，必须记录最近终止节点，两个问题不可混用。
- 返回索引或全部并列source时，需要在节点加代表ID或终止子树信息；不能在当前只存字符边的结构中凭空恢复所有匹配来源。source重复不影响最大长度，但影响列出来源的多重性。
- 大型索引可考虑压缩Trie或排序后查询相邻候选，权衡指针开销与构建成本。固定source多次查询可以复用索引；样例函数为演示一次构建加批量查询，不为每项query重建。
手动走一遍
source=[flower,flow,flight]，queries=[flute,flowing,z,空串]，结果[2,4,0,0]。flowing与flow匹配4字符；flower下一字符e与i不同，不能继续。source=[a]、query=abc结果1，不要求query整体被包含。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""For every query string, return its longest common prefix with any source string."""
def longest_prefix_lengths(source, queries):
root = {}
for word in source:
node = root
for char in word:
node = node.setdefault(char, {})
result = []
for word in queries:
node = root
matched = 0
for char in word:
if char not in node:
break
node = node[char]
matched += 1
result.append(matched)
return result
复杂度
设source总字符数S、query总字符数Q，哈希子节点期望 O(S+Q) 时间，Trie空间 O(S)，答案 O(query个数)。Unicode归一化或大小写折叠属于额外预处理合同。
易错点与追问
容易失分的边界
- 把公共前缀误写成完整单词匹配。
- 把每项答案擅自改成全局最大值。
- source为空导致max空集合错误。
- 数字输入默认忽略负号。
继续深挖
- 如何返回匹配的source ID？
- 若要最长完整单词前缀怎么改？
- source频繁删除怎样维护节点引用计数？
- 排序加二分与Trie在内存上的取舍？
