LeetCode 题解工作台
最长公共后缀查询
给你两个字符串数组 wordsContainer 和 wordsQuery 。 对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·string
答案摘要
题目需要我们找到最长公共后缀，我们可以考虑使用字典树。 我们定义字典树的节点结构如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你两个字符串数组 wordsContainer 和 wordsQuery 。
对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。
请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。
示例 1：
输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
输出：[1,1,1]
解释：
我们分别来看每一个 wordsQuery[i] ：
- 对于
wordsQuery[0] = "cd"，wordsContainer中有最长公共后缀"cd"的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。 - 对于
wordsQuery[1] = "bcd"，wordsContainer中有最长公共后缀"bcd"的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。 - 对于
wordsQuery[2] = "xyz"，wordsContainer中没有字符串跟它有公共后缀，所以最长公共后缀为""，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
示例 2：
输入：wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
输出：[2,0,2]
解释：
我们分别来看每一个 wordsQuery[i] ：
- 对于
wordsQuery[0] = "gh"，wordsContainer中有最长公共后缀"gh"的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。 - 对于
wordsQuery[1] = "acbfgh"，只有下标为 0 的字符串有最长公共后缀"fgh"。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。 - 对于
wordsQuery[2] = "acbfegh"，wordsContainer中有最长公共后缀"gh"的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
提示：
1 <= wordsContainer.length, wordsQuery.length <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i]只包含小写英文字母。wordsQuery[i]只包含小写英文字母。wordsContainer[i].length的和至多为5 * 105。wordsQuery[i].length的和至多为5 * 105。
解题思路
方法一：字典树
题目需要我们找到最长公共后缀，我们可以考虑使用字典树。
我们定义字典树的节点结构如下：
children：一个长度为 26 的数组，用于存储子节点。length：当前节点的最短字符串长度。idx：当前节点的字符串下标。
我们遍历字符串数组 wordsContainer，将每个字符串倒序插入字典树中。在插入的过程中，我们更新每个节点的 length 和 idx。
接下来，我们遍历字符串数组 wordsQuery，对于每个字符串，我们从字典树中查找最长公共后缀的字符串下标，在寻找的过程中，如果遇到空节点，说明往后没有公共后缀了，我们可以直接返回当前节点的 idx。
时间复杂度 ，空间复杂度 ，其中 和 分别是 wordsContainer 和 wordsQuery 的字符串长度之和；而 是字符集大小，本题中 。
class Trie:
__slots__ = ("children", "length", "idx")
def __init__(self):
self.children = [None] * 26
self.length = inf
self.idx = inf
def insert(self, w: str, i: int):
node = self
if node.length > len(w):
node.length = len(w)
node.idx = i
for c in w[::-1]:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
if node.length > len(w):
node.length = len(w)
node.idx = i
def query(self, w: str) -> int:
node = self
for c in w[::-1]:
idx = ord(c) - ord("a")
if node.children[idx] is None:
break
node = node.children[idx]
return node.idx
class Solution:
def stringIndices(
self, wordsContainer: List[str], wordsQuery: List[str]
) -> List[int]:
trie = Trie()
for i, w in enumerate(wordsContainer):
trie.insert(w, i)
return [trie.query(w) for w in wordsQuery]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on total characters in wordsContainer and wordsQuery for building and traversing the trie, roughly O(sum of lengths). Space complexity is also O(sum of lengths) for the trie structure. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
You are reversing strings to simplify the suffix problem.
- question_mark
You need to track multiple tie-breaking rules: length and index.
- question_mark
Efficient matching requires a trie or hashmap, naive comparisons will timeout.
常见陷阱
外企场景- error
Ignoring tie-breaker rules can yield incorrect indices.
- error
Using naive suffix comparison for every query causes timeouts.
- error
Forgetting to reverse strings before building the trie changes logic.
进阶变体
外企场景- arrow_right_alt
Find longest common suffix with at most k mismatches.
- arrow_right_alt
Return the actual matching string instead of index.
- arrow_right_alt
Handle dynamic insertion and deletion in wordsContainer.