class Solution {
public:
vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
}
};
100268. 最长公共后缀查询
给你两个字符串数组 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 。原站题解
python3 解法, 执行用时: 2021 ms, 内存消耗: 180.1 MB, 提交时间: 2024-03-24 23:04:55
class Node:
__slots__ = 'son', 'min_l', 'i'
def __init__(self):
self.son = [None] * 26
self.min_l = inf
class Solution:
def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
ord_a = ord('a')
root = Node()
for idx, s in enumerate(wordsContainer):
l = len(s)
cur = root
if l < cur.min_l:
cur.min_l, cur.i = l, idx
for c in map(ord, reversed(s)):
c -= ord_a
if cur.son[c] is None:
cur.son[c] = Node()
cur = cur.son[c]
if l < cur.min_l:
cur.min_l, cur.i = l, idx
ans = []
for s in wordsQuery:
cur = root
for c in map(ord, reversed(s)):
c -= ord_a
if cur.son[c] is None:
break
cur = cur.son[c]
ans.append(cur.i)
return ans
java 解法, 执行用时: 61 ms, 内存消耗: 151.9 MB, 提交时间: 2024-03-24 23:04:35
class Node {
Node[] son = new Node[26];
int minL = Integer.MAX_VALUE;
int i;
}
class Solution {
public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
Node root = new Node();
for (int idx = 0; idx < wordsContainer.length; ++idx) {
char[] s = wordsContainer[idx].toCharArray();
int l = s.length;
Node cur = root;
if (l < cur.minL) {
cur.minL = l;
cur.i = idx;
}
for (int i = s.length - 1; i >= 0; i--) {
int b = s[i] - 'a';
if (cur.son[b] == null) {
cur.son[b] = new Node();
}
cur = cur.son[b];
if (l < cur.minL) {
cur.minL = l;
cur.i = idx;
}
}
}
int[] ans = new int[wordsQuery.length];
for (int idx = 0; idx < wordsQuery.length; idx++) {
char[] s = wordsQuery[idx].toCharArray();
Node cur = root;
for (int i = s.length - 1; i >= 0 && cur.son[s[i] - 'a'] != null; i--) {
cur = cur.son[s[i] - 'a'];
}
ans[idx] = cur.i;
}
return ans;
}
}
cpp 解法, 执行用时: 424 ms, 内存消耗: 799.2 MB, 提交时间: 2024-03-24 23:04:23
struct Node {
Node *son[26]{};
int min_l = INT_MAX, i;
};
class Solution {
public:
vector<int> stringIndices(vector<string> &wordsContainer, vector<string> &wordsQuery) {
Node *root = new Node();
for (int idx = 0; idx < wordsContainer.size(); ++idx) {
auto &s = wordsContainer[idx];
int l = s.length();
auto cur = root;
if (l < cur->min_l) {
cur->min_l = l;
cur->i = idx;
}
for (int i = s.length() - 1; i >= 0; i--) {
int b = s[i] - 'a';
if (cur->son[b] == nullptr) {
cur->son[b] = new Node();
}
cur = cur->son[b];
if (l < cur->min_l) {
cur->min_l = l;
cur->i = idx;
}
}
}
vector<int> ans;
ans.reserve(wordsQuery.size());
for (auto &s: wordsQuery) {
auto cur = root;
for (int i = s.length() - 1; i >= 0 && cur->son[s[i] - 'a']; i--) {
cur = cur->son[s[i] - 'a'];
}
ans.push_back(cur->i);
}
return ans;
}
};
golang 解法, 执行用时: 265 ms, 内存消耗: 173.8 MB, 提交时间: 2024-03-24 23:04:09
func stringIndices(wordsContainer, wordsQuery []string) []int {
type node struct {
son [26]*node
minL, i int
}
root := &node{minL: math.MaxInt}
for idx, s := range wordsContainer {
l := len(s)
cur := root
if l < cur.minL {
cur.minL, cur.i = l, idx
}
for i := len(s) - 1; i >= 0; i-- {
b := s[i] - 'a'
if cur.son[b] == nil {
cur.son[b] = &node{minL: math.MaxInt}
}
cur = cur.son[b]
if l < cur.minL {
cur.minL, cur.i = l, idx
}
}
}
ans := make([]int, len(wordsQuery))
for idx, s := range wordsQuery {
cur := root
for i := len(s) - 1; i >= 0 && cur.son[s[i]-'a'] != nil; i-- {
cur = cur.son[s[i]-'a']
}
ans[idx] = cur.i
}
return ans
}