title
相关企业
提示
给你两个字符串数组 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。
solution
字典树题目，字典树节点上额外维护最小长度的string index，这样search这个Trie树时可以直接返回这个index。
class TrieNode:
def __init__(self):
self.precount = 0
self.count = 0
self.children = {}
self.min_l = float('inf')
self.index = 0
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.precount += 1
node.count += 1
def insert2(self, word: str, i, l) -> None:
"""
Inserts a word into the trie.
记录下word的index以及当前子树最小的index
"""
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
if node.min_l > l:
node.min_l = l
node.index = i
node = node.children[c]
node.precount += 1
if node.min_l > l:
node.min_l = l
node.index = i
node.count += 1
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.count > 0
def search2(self, word: str) -> int:
"""
找最长公共前缀的对应字符串index
"""
node = self.root
for c in word:
if c not in node.children:
return node.index
node = node.children[c]
return node.index
def searchPrefix(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for i, c in enumerate(word):
if c not in node.children:
return word[:i]
node = node.children[c]
return word
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return node.precount > 0
class Solution:
def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
a = [w[::-1] for w in wordsContainer]
b = [w[::-1] for w in wordsQuery]
# print(a, b)
trie = Trie()
for i, w in enumerate(a):
trie.insert2(w, i, len(w))
ans = []
for w in b:
r = trie.search2(w)
ans.append(r)
return ans