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 integersans, whereans[i]is the index of the string inwordsContainerthat has thelongest common suffix with wordsQuery[i].
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 from `wordsContainer` that 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 from `wordsContainer` that 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 from `wordsContainer` that shares a common suffix. Hence the longest common suffix is`""`, that issharedwith 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.
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 from `wordsContainer` that 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 2is shorter.* For `wordsQuery[2] = "acbfegh"`, strings from `wordsContainer` that 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.
The problem requires finding the longest common suffix for each query, which naturally leads us to use a Trie data structure. However, since we need to match suffixes (not prefixes), we process all strings in reverse order when building and searching the Trie.
The key insight is to store at each Trie node the index of the best candidate word that can be reached through that path. The “best” candidate follows the tie-breaking rules: prefer longer common suffix, then shorter word length, then earlier index in the original array.
Initialize the Trie: Create a root node that initially points to the shortest word in wordsContainer (tie-broken by earliest index).
Build the Trie: For each word in wordsContainer, insert it into the Trie by traversing from the last character to the first (reverse order). At each node during insertion:
If the node doesn’t exist, create it with the current word’s index
If the node exists, update its stored index if the current word is shorter than the previously stored word
Process Queries: For each query word, traverse the Trie from the last character to the first:
Start with the root’s stored index as the current best answer
At each step, if we can continue in the Trie, update the answer to the current node’s stored index
If we can’t continue further, return the last valid answer
This ensures we get the longest possible suffix match with proper tie-breaking
Note on C++ code: The TrieNode destructor recursively deletes all child nodes, ensuring proper memory cleanup. This is crucial for avoiding memory leaks, especially with large test cases where the Trie can grow significantly.
#include<vector>#include<string>usingnamespace std;
structTrieNode {
int index;
TrieNode* children[26];
TrieNode(int idx =-1) : index(idx) {
for (int i =0; i <26; i++) {
children[i] =nullptr;
}
}
~TrieNode() {
for (int i =0; i <26; i++) {
if (children[i]) {
delete children[i];
}
}
}
};
classSolution {
private:void addWord(TrieNode* root, const vector<string>& wordsContainer, int wordIndex) {
TrieNode* node = root;
const string& word = wordsContainer[wordIndex];
// Traverse from last character to first (reverse order for suffix matching)
for (int i = word.length() -1; i >=0; i--) {
int charIndex = word[i] -'a';
if (node->children[charIndex] ==nullptr) {
node->children[charIndex] =new TrieNode(wordIndex);
}
node = node->children[charIndex];
// Update index if current word is shorter (better candidate)
if (wordsContainer[node->index].length() > wordsContainer[wordIndex].length()) {
node->index = wordIndex;
}
}
}
intsearchQuery(TrieNode* root, const string& query) {
TrieNode* node = root;
int bestIndex = root->index; // Start with root's stored index
// Traverse from last character to first
for (int i = query.length() -1; i >=0; i--) {
int charIndex = query[i] -'a';
if (node->children[charIndex] ==nullptr) {
break; // Can't continue further
}
node = node->children[charIndex];
bestIndex = node->index; // Update to current node's stored index
}
return bestIndex;
}
public: vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
// Initialize root with index of shortest word (tie-broken by earliest index)
int shortestIndex =0;
for (int i =1; i < wordsContainer.size(); i++) {
if (wordsContainer[i].length() < wordsContainer[shortestIndex].length()) {
shortestIndex = i;
}
}
TrieNode* root =new TrieNode(shortestIndex);
// Build trie with all words
for (int i =0; i < wordsContainer.size(); i++) {
addWord(root, wordsContainer, i);
}
// Process all queries
vector<int> result;
result.reserve(wordsQuery.size());
for (const string& query : wordsQuery) {
result.push_back(searchQuery(root, query));
}
// Clean up memory - destructor will recursively delete all nodes
delete root;
return result;
}
};
classTrieNode {
int index;
TrieNode[] children;
publicTrieNode(int idx) {
this.index= idx;
this.children=new TrieNode[26];
}
}
classSolution {
privatevoidaddWord(TrieNode root, String[] wordsContainer, int wordIndex) {
TrieNode node = root;
String word = wordsContainer[wordIndex];
// Traverse from last character to first (reverse order for suffix matching)for (int i = word.length() - 1; i >= 0; i--) {
int charIndex = word.charAt(i) -'a';
if (node.children[charIndex]==null) {
node.children[charIndex]=new TrieNode(wordIndex);
}
node = node.children[charIndex];
// Update index if current word is shorter (better candidate)if (wordsContainer[node.index].length() > wordsContainer[wordIndex].length()) {
node.index= wordIndex;
}
}
}
privateintsearchQuery(TrieNode root, String query) {
TrieNode node = root;
int bestIndex = root.index; // Start with root's stored index// Traverse from last character to firstfor (int i = query.length() - 1; i >= 0; i--) {
int charIndex = query.charAt(i) -'a';
if (node.children[charIndex]==null) {
break; // Can't continue further }
node = node.children[charIndex];
bestIndex = node.index; // Update to current node's stored index }
return bestIndex;
}
publicint[]stringIndices(String[] wordsContainer, String[] wordsQuery) {
// Initialize root with index of shortest word (tie-broken by earliest index)int shortestIndex = 0;
for (int i = 1; i < wordsContainer.length; i++) {
if (wordsContainer[i].length() < wordsContainer[shortestIndex].length()) {
shortestIndex = i;
}
}
TrieNode root =new TrieNode(shortestIndex);
// Build trie with all wordsfor (int i = 0; i < wordsContainer.length; i++) {
addWord(root, wordsContainer, i);
}
// Process all queriesint[] result =newint[wordsQuery.length];
for (int i = 0; i < wordsQuery.length; i++) {
result[i]= searchQuery(root, wordsQuery[i]);
}
return result;
}
}
classTrieNode(var index: Int = -1) {
val children = Array<TrieNode?>(26) { null }
}
classSolution {
privatefunaddWord(root: TrieNode, wordsContainer: Array<String>, wordIndex: Int) {
var node = root
val word = wordsContainer[wordIndex]
// Traverse from last character to first (reverse order for suffix matching)
for (i in word.length - 1 downTo 0) {
val charIndex = word[i] - 'a'if (node.children[charIndex] ==null) {
node.children[charIndex] = TrieNode(wordIndex)
}
node = node.children[charIndex]!!// Update index if current word is shorter (better candidate)
if (wordsContainer[node.index].length > wordsContainer[wordIndex].length) {
node.index = wordIndex
}
}
}
privatefunsearchQuery(root: TrieNode, query: String): Int {
var node = root
var bestIndex = root.index // Start with root's stored index
// Traverse from last character to first
for (i in query.length - 1 downTo 0) {
val charIndex = query[i] - 'a'if (node.children[charIndex] ==null) {
break// Can't continue further
}
node = node.children[charIndex]!! bestIndex = node.index // Update to current node's stored index
}
return bestIndex
}
funstringIndices(wordsContainer: Array<String>, wordsQuery: Array<String>): IntArray {
// Initialize root with index of shortest word (tie-broken by earliest index)
var shortestIndex = 0for (i in1 until wordsContainer.size) {
if (wordsContainer[i].length < wordsContainer[shortestIndex].length) {
shortestIndex = i
}
}
val root = TrieNode(shortestIndex)
// Build trie with all words
for (i in wordsContainer.indices) {
addWord(root, wordsContainer, i)
}
// Process all queries
val result = IntArray(wordsQuery.size)
for (i in wordsQuery.indices) {
result[i] = searchQuery(root, wordsQuery[i])
}
return result
}
}
classTrieNode:
def__init__(self, index=-1):
self.children = {}
self.index = index
classSolution:
defaddWord(self, root: TrieNode, wordsContainer: list[str], wordIndex: int):
node = root
word = wordsContainer[wordIndex]
# Traverse from last character to first (reverse order for suffix matching)for i in range(len(word) -1, -1, -1):
char = word[i]
if char notin node.children:
node.children[char] = TrieNode(wordIndex)
node = node.children[char]
# Update index if current word is shorter (better candidate)if len(wordsContainer[node.index]) > len(wordsContainer[wordIndex]):
node.index = wordIndex
defsearchQuery(self, root: TrieNode, query: str) -> int:
node = root
bestIndex = root.index # Start with root's stored index# Traverse from last character to firstfor i in range(len(query) -1, -1, -1):
char = query[i]
if char notin node.children:
break# Can't continue further node = node.children[char]
bestIndex = node.index # Update to current node's stored indexreturn bestIndex
defstringIndices(self, wordsContainer: list[str], wordsQuery: list[str]) -> list[int]:
# Initialize root with index of shortest word (tie-broken by earliest index) shortestIndex =0for i in range(1, len(wordsContainer)):
if len(wordsContainer[i]) < len(wordsContainer[shortestIndex]):
shortestIndex = i
root = TrieNode(shortestIndex)
# Build trie with all wordsfor i in range(len(wordsContainer)):
self.addWord(root, wordsContainer, i)
# Process all queries result = []
for query in wordsQuery:
result.append(self.searchQuery(root, query))
return result
structTrieNode {
index: i32,
children: [Option<Box<TrieNode>>; 26],
}
impl TrieNode {
fnnew(index: i32) -> Self {
TrieNode {
index,
children: Default::default(),
}
}
}
impl Solution {
fnadd_word(root: &mut TrieNode, words_container: &[String], word_index: usize) {
letmut node = root;
let word =&words_container[word_index];
// Traverse from last character to first (reverse order for suffix matching)
for ch in word.chars().rev() {
let char_index = (ch asu8-b'a') asusize;
if node.children[char_index].is_none() {
node.children[char_index] = Some(Box::new(TrieNode::new(word_index asi32)));
}
node = node.children[char_index].as_mut().unwrap();
// Update index if current word is shorter (better candidate)
if words_container[node.index asusize].len() > words_container[word_index].len() {
node.index = word_index asi32;
}
}
}
fnsearch_query(root: &TrieNode, query: &str) -> i32 {
letmut node = root;
letmut best_index = root.index; // Start with root's stored index
// Traverse from last character to first
for ch in query.chars().rev() {
let char_index = (ch asu8-b'a') asusize;
if node.children[char_index].is_none() {
break; // Can't continue further
}
node = node.children[char_index].as_ref().unwrap();
best_index = node.index; // Update to current node's stored index
}
best_index
}
pubfnstring_indices(words_container: Vec<String>, words_query: Vec<String>) -> Vec<i32> {
// Initialize root with index of shortest word (tie-broken by earliest index)
letmut shortest_index =0;
for i in1..words_container.len() {
if words_container[i].len() < words_container[shortest_index].len() {
shortest_index = i;
}
}
letmut root = TrieNode::new(shortest_index asi32);
// Build trie with all words
for i in0..words_container.len() {
Self::add_word(&mut root, &words_container, i);
}
// Process all queries
letmut result = Vec::with_capacity(words_query.len());
for query in&words_query {
result.push(Self::search_query(&root, query));
}
result
}
}
classTrieNode {
index: number;
children: (TrieNode|null)[];
constructor(index: number=-1) {
this.index=index;
this.children=new Array(26).fill(null);
}
}
functionaddWord(root: TrieNode, wordsContainer: string[], wordIndex: number):void {
letnode=root;
constword=wordsContainer[wordIndex];
// Traverse from last character to first (reverse order for suffix matching)
for (leti=word.length-1; i>=0; i--) {
constcharIndex=word.charCodeAt(i) -97; // 'a'.charCodeAt(0)
if (node.children[charIndex] ===null) {
node.children[charIndex] =newTrieNode(wordIndex);
}
node=node.children[charIndex]!;
// Update index if current word is shorter (better candidate)
if (wordsContainer[node.index].length>wordsContainer[wordIndex].length) {
node.index=wordIndex;
}
}
}
functionsearchQuery(root: TrieNode, query: string):number {
letnode=root;
letbestIndex=root.index; // Start with root's stored index
// Traverse from last character to first
for (leti=query.length-1; i>=0; i--) {
constcharIndex=query.charCodeAt(i) -97; // 'a'.charCodeAt(0)
if (node.children[charIndex] ===null) {
break; // Can't continue further
}
node=node.children[charIndex]!;
bestIndex=node.index; // Update to current node's stored index
}
returnbestIndex;
}
functionstringIndices(wordsContainer: string[], wordsQuery: string[]):number[] {
// Initialize root with index of shortest word (tie-broken by earliest index)
letshortestIndex=0;
for (leti=1; i<wordsContainer.length; i++) {
if (wordsContainer[i].length<wordsContainer[shortestIndex].length) {
shortestIndex=i;
}
}
constroot=newTrieNode(shortestIndex);
// Build trie with all words
for (leti=0; i<wordsContainer.length; i++) {
addWord(root, wordsContainer, i);
}
// Process all queries
constresult: number[] = [];
for (constqueryofwordsQuery) {
result.push(searchQuery(root, query));
}
returnresult;
}
⏰ Time complexity: O(N × L + Q × L), where N is the number of words in wordsContainer, Q is the number of queries in wordsQuery, and L is the maximum word length.
Building the Trie: O(N × L) - Each of the N words is processed character by character (up to L characters)
Processing queries: O(Q × L) - Each of the Q queries traverses the Trie up to L levels deep
Finding shortest word: O(N) - Linear scan through wordsContainer (absorbed into the dominant terms)
🧺 Space complexity: O(N × L), for storing the Trie structure. In the worst case, when no words share common suffixes, we create unique paths for each word, resulting in N × L nodes total.