Description
You are given two arrays of strings wordsContainer and wordsQuery.
For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer.
Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].
Example 1:
Input: wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]
Output: [1,1,1]
Explanation:
Let's look at each wordsQuery[i] separately:
- For
wordsQuery[0] = "cd", strings fromwordsContainerthat share the longest common suffix"cd"are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3. - For
wordsQuery[1] = "bcd", strings fromwordsContainerthat share the longest common suffix"bcd"are at indices 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3. - For
wordsQuery[2] = "xyz", there is no string fromwordsContainerthat shares a common suffix. Hence the longest common suffix is"", that is shared with strings at index 0, 1, and 2. Among these, the answer is the string at index 1 because it has the shortest length of 3.
Example 2:
Input: wordsContainer = ["abcdefgh","poiuygh","ghghgh"], wordsQuery = ["gh","acbfgh","acbfegh"]
Output: [2,0,2]
Explanation:
Let's look at each wordsQuery[i] separately:
- For
wordsQuery[0] = "gh", strings fromwordsContainerthat share the longest common suffix"gh"are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6. - For
wordsQuery[1] = "acbfgh", only the string at index 0 shares the longest common suffix"fgh". Hence it is the answer, even though the string at index 2 is shorter. - For
wordsQuery[2] = "acbfegh", strings fromwordsContainerthat share the longest common suffix"gh"are at indices 0, 1, and 2. Among these, the answer is the string at index 2 because it has the shortest length of 6.
Constraints:
1 <= wordsContainer.length, wordsQuery.length <= 1041 <= wordsContainer[i].length <= 5 * 1031 <= wordsQuery[i].length <= 5 * 103wordsContainer[i]consists only of lowercase English letters.wordsQuery[i]consists only of lowercase English letters.- Sum of
wordsContainer[i].lengthis at most5 * 105. - Sum of
wordsQuery[i].lengthis at most5 * 105.
Solutions
This code finds the best matching word in wordsContainer for each search word in wordsQuery by looking for the longest shared ending (suffix). It does this efficiently by building a search tree (called a Trie) and inserting the container words backward, from right to left. As it builds the tree, each node keeps track of the "best" word index that shares that suffix, prioritizing shorter words and using the earliest-appearing word as a tiebreaker. Finally, for each query, the code traverses the tree backward to find the longest matching suffix path possible and retrieves its stored index; if no characters match at all, it automatically falls back to the index of the overall shortest and earliest word in the container.
/**
* @param {string[]} wordsContainer
* @param {string[]} wordsQuery
* @return {number[]}
*/
var stringIndices = function (wordsContainer, wordsQuery) {
const root = {
children: {},
bestIndex: 0,
};
for (let i = 0; i < wordsContainer.length; i++) {
const word = wordsContainer[i];
let node = root;
if (word.length < wordsContainer[node.bestIndex].length || (word.length === wordsContainer[node.bestIndex].length && i < node.bestIndex)) {
node.bestIndex = i;
}
for (let j = word.length - 1; j >= 0; j--) {
const char = word[j];
let child = node.children[char];
if (!child) {
child = {
children: {},
bestIndex: i,
};
node.children[char] = child;
}
node = child;
if (word.length < wordsContainer[node.bestIndex].length || (word.length === wordsContainer[node.bestIndex].length && i < node.bestIndex)) {
node.bestIndex = i;
}
}
}
const n = wordsQuery.length;
const result = Array(n);
for (let i = 0; i < n; i++) {
let node = root;
let bestIndex = root.bestIndex;
for (let j = wordsQuery[i].length - 1; j >= 0; j--) {
const next = node.children[wordsQuery[i][j]];
if (!next) {
break;
}
node = next;
bestIndex = node.bestIndex;
}
result[i] = bestIndex;
}
return result;
};