Problem

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 inwordsContainer that has thelongest common suffix with wordsQuery[i].

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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 2 is 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.

Constraints

  • 1 <= wordsContainer.length, wordsQuery.length <= 10^4
  • 1 <= wordsContainer[i].length <= 5 * 10^3
  • 1 <= wordsQuery[i].length <= 5 * 10^3
  • wordsContainer[i] consists only of lowercase English letters.
  • wordsQuery[i] consists only of lowercase English letters.
  • Sum of wordsContainer[i].length is at most 5 * 10^5.
  • Sum of wordsQuery[i].length is at most 5 * 10^5.

Solution

Method 1 – Trie on Reversed Strings (1)

Intuition

To efficiently find the longest common suffix, we can build a trie using the reversed strings from wordsContainer. For each query, we reverse it and traverse the trie to find the deepest match, keeping track of the best candidate index, length, and tie-breaking by length and order.

Approach

  1. Reverse all strings in wordsContainer and build a trie, storing at each node the best candidate index and length so far.
  2. For each query, reverse it and traverse the trie as far as possible, tracking the best candidate index (longest match, shortest length, earliest index).
  3. Return the index for each query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

struct TrieNode {
    vector<TrieNode*> children;
    int idx, len;
    TrieNode() : children(26, nullptr), idx(-1), len(0) {}
};
class Solution {
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < wordsContainer.size(); ++i) {
            string s = wordsContainer[i];
            reverse(s.begin(), s.end());
            TrieNode* node = root;
            for (char c : s) {
                int d = c - 'a';
                if (!node->children[d]) node->children[d] = new TrieNode();
                node = node->children[d];
                if (node->len < s.size() || (node->len == s.size() && node->idx > i)) {
                    node->len = s.size();
                    node->idx = i;
                }
            }
        }
        vector<int> ans;
        for (int q = 0; q < wordsQuery.size(); ++q) {
            string s = wordsQuery[q];
            reverse(s.begin(), s.end());
            TrieNode* node = root;
            int best = -1, bestLen = -1, bestIdx = wordsContainer.size();
            for (int i = 0; i < s.size(); ++i) {
                int d = s[i] - 'a';
                if (!node->children[d]) break;
                node = node->children[d];
                if (node->idx != -1 && (i+1 > bestLen || (i+1 == bestLen && (wordsContainer[node->idx].size() < wordsContainer[best].size() || (wordsContainer[node->idx].size() == wordsContainer[best].size() && node->idx < best))))) {
                    best = node->idx;
                    bestLen = i+1;
                }
            }
            if (best == -1) best = 0;
            ans.push_back(best);
        }
        return ans;
    }
};
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class TrieNode:
    def __init__(self):
        self.children = {}
        self.idx = -1
        self.len = 0
class Solution:
    def stringIndices(self, wordsContainer: list[str], wordsQuery: list[str]) -> list[int]:
        root = TrieNode()
        for i, w in enumerate(wordsContainer):
            s = w[::-1]
            node = root
            for c in s:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
                if node.len < len(w) or (node.len == len(w) and node.idx > i):
                    node.len = len(w)
                    node.idx = i
        ans = []
        for q in wordsQuery:
            s = q[::-1]
            node = root
            best = -1
            bestLen = -1
            for i, c in enumerate(s):
                if c not in node.children:
                    break
                node = node.children[c]
                if node.idx != -1 and (i+1 > bestLen or (i+1 == bestLen and (len(wordsContainer[node.idx]) < len(wordsContainer[best]) if best != -1 else True) or (i+1 == bestLen and len(wordsContainer[node.idx]) == len(wordsContainer[best]) and node.idx < best))):
                    best = node.idx
                    bestLen = i+1
            if best == -1:
                best = 0
            ans.append(best)
        return ans
1

// Omitted for brevity. See Python for main logic.

1

// Omitted for brevity. See Python for main logic.

Complexity

  • ⏰ Time complexity: O(NL + QL), where N is the number of words in wordsContainer, Q is the number of queries, and L is the average word length. Each word and query is processed once.
  • 🧺 Space complexity: O(NL), for the trie.