Facebook Pixel

3093. Longest Common Suffix Queries

HardTrieArrayString
Leetcode Link

Problem 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].

Intuition

To solve this problem, we need to efficiently determine the longest common suffix between strings in two arrays, wordsContainer and wordsQuery. The nature of the problem suggests that a data structure like a Trie can be beneficial, especially since we are dealing with suffixes.

The key idea is to store each string in wordsContainer in a Trie but in reversed order, allowing us to easily match suffixes by traversing the Trie. Each node of the Trie keeps track of the shortest string length and its index where it was first encountered. When we insert strings into this Trie, we ensure it captures the hierarchy of suffixes.

For querying, we also reverse each query string to see how far into the Trie we can traverse, thus identifying the longest suffix match. The information stored in the Trie nodes helps us resolve ties by prioritizing shortest lengths and earlier occurrences.

This approach leverages the Trieโ€™s ability to share common prefixes (or in this case, reversed suffixes), making it highly efficient for lookups once the Trie is constructed.

Learn more about Trie patterns.

Solution Approach

Solution 1: Trie

The solution employs a Trie to handle the problem of finding the longest common suffix efficiently.

  1. Trie Structure:

    • Each Trie node contains three key attributes:
      • children: An array of length 26, representing each letter of the alphabet.
      • length: Stores the length of the shortest string that reaches the current node.
      • idx: Holds the index of the string that first reached this node and shares this suffix.

  2. Insertion:

    • For each string in wordsContainer, insert the string into the Trie in reverse order.
    • During insertion, update the length and idx in each node to reflect the shortest length and first occurrence.

  3. Querying:

    • To find the string from wordsContainer with the longest common suffix with a given wordsQuery[i], reverse wordsQuery[i] and traverse the Trie.
    • Traverse the Trie from root using the reversed string. The traversal continues as long as children nodes exist corresponding to the characters in the suffix.
    • Once the path is exhausted, or no further match can proceed, the idx stored in the current node provides the index of the string in wordsContainer with the longest suffix match.

This solution is efficient due to the Trieโ€™s ability to quickly manage and retrieve suffix matches, taking advantage of shared path structures inherent in the Trie data structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach using the Trie data structure.

Given:

  • wordsContainer = ["hello", "world", "card", "hard"]
  • wordsQuery = ["bold", "yard", "gold"]

Steps:

  1. Insert strings from wordsContainer into the Trie in reverse order:

    • Insert "hello" (olleh) into the Trie:

      • o -> l -> l -> e -> h
      • At each node, update length and idx. For "olleh", length becomes 5, and idx becomes 0.

    • Insert "world" (dlrow):

      • d -> l -> r -> o -> w
      • Update the nodes accordingly, with length being 5 and idx 1.

    • Insert "card" (drac):

      • d -> r -> a -> c
      • Nodes update length to 4 and idx to 2, as this is the first "drac".

    • Insert "hard" (drah):

      • d -> r -> a -> h
      • Nodes update length and idx only if a shorter length or earlier occurrence is found. Since itโ€™s not, idx remains 2 until the new path h is instantiated.

  2. Query each string in wordsQuery:

    • Query "bold" (dlob):

      • Traverse d in the Trie. As we try to traverse l, we find no further match in "dlrow".
      • The node at d corresponds to drac index 2, making "card" the longest common suffix match as itโ€™s shortest.

    • Query "yard" (dray):

      • Traverse d -> r -> a. Unable to find y.
      • drac ("card") and drah ("hard") share the path. "card" at index 2 is chosen due to being shorter.

    • Query "gold" (dlog):

      • Traverse d -> l. o is available matching the path of dlrow.
      • On reaching l, no further match. "world" (index 1) is the match.

Result:

  • ans = [2, 2, 1]

The example demonstrates how the Trie efficiently handles suffix match lookups by reversing the strings and leveraging shared path structures in the Trie.

Solution Implementation

1from typing import List
2from math import inf
3
4class Trie:
5    __slots__ = ("children", "length", "idx")
6
7    def __init__(self):
8        # Initializes an array to store children nodes (one for each letter a-z)
9        self.children = [None] * 26
10        # Initializes length and index with infinity to represent a default state
11        self.length = inf
12        self.idx = inf
13
14    def insert(self, word: str, index: int):
15        # Starts insertion process at root
16        node = self
17        # Update node's length and index if current word is shorter
18        if node.length > len(word):
19            node.length = len(word)
20            node.idx = index
21        # Iterate over the word from the last character to the first
22        for char in word[::-1]:
23            idx = ord(char) - ord("a")  # Calculate position in alphabet
24            # If the current character's node doesn't exist, create a new Trie node
25            if node.children[idx] is None:
26                node.children[idx] = Trie()
27            node = node.children[idx]
28            # Update node's length and index with the current word's properties, if applicable
29            if node.length > len(word):
30                node.length = len(word)
31                node.idx = index
32
33    def query(self, word: str) -> int:
34        # Start query process at the root
35        node = self
36        # Iterate over the word from the last character to the first
37        for char in word[::-1]:
38            idx = ord(char) - ord("a")  # Calculate position in alphabet
39            # Break if there's no node for the current character
40            if node.children[idx] is None:
41                break
42            node = node.children[idx]
43        # Return the index of the word or inf if not found
44        return node.idx
45
46
47class Solution:
48    def stringIndices(
49        self, wordsContainer: List[str], wordsQuery: List[str]
50    ) -> List[int]:
51        # Instantiate the Trie object
52        trie = Trie()
53        # Insert each word into the trie along with its index
54        for i, word in enumerate(wordsContainer):
55            trie.insert(word, i)
56        # Query the trie for each word in wordsQuery and return the indices
57        return [trie.query(word) for word in wordsQuery]
58
1class Trie {
2    private static final int INFINITY = 1 << 30; // Represents an infinite value for comparison
3    private Trie[] children = new Trie[26]; // Array to store child nodes for each character 'a' to 'z'
4    private int length = INFINITY; // Minimum length of the words inserted
5    private int index = INFINITY; // Index of the word with minimum length inserted
6
7    // Inserts a word `w` with its index `i` into the Trie
8    public void insert(String w, int i) {
9        Trie node = this;
10        if (node.length > w.length()) {
11            node.length = w.length();
12            node.index = i;
13        }
14        // Traverse the word from the end to the beginning
15        for (int k = w.length() - 1; k >= 0; --k) {
16            int charIndex = w.charAt(k) - 'a'; // Calculate the current character's index
17            if (node.children[charIndex] == null) {
18                node.children[charIndex] = new Trie(); // Create a new Trie node if not present
19            }
20            node = node.children[charIndex];
21            if (node.length > w.length()) {
22                node.length = w.length();
23                node.index = i;
24            }
25        }
26    }
27
28    // Queries the Trie for the longest suffix match of word `w`
29    public int query(String w) {
30        Trie node = this;
31        for (int k = w.length() - 1; k >= 0; --k) {
32            int charIndex = w.charAt(k) - 'a';
33            if (node.children[charIndex] == null) {
34                break; // Stop if no further match is found
35            }
36            node = node.children[charIndex];
37        }
38        return node.index; // Return the index of the best match found
39    }
40}
41
42class Solution {
43    // Function to return indices of the longest matching suffixes from `wordsContainer` for each word in `wordsQuery`
44    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
45        Trie trie = new Trie(); // Initialize the Trie
46
47        // Insert each word from `wordsContainer` into the Trie with its index
48        for (int i = 0; i < wordsContainer.length; ++i) {
49            trie.insert(wordsContainer[i], i);
50        }
51
52        int queryCount = wordsQuery.length; 
53        int[] results = new int[queryCount]; // Array to store results for each query
54
55        // Retrieve the best match index for each query contained in `wordsQuery`
56        for (int i = 0; i < queryCount; ++i) {
57            results[i] = trie.query(wordsQuery[i]);
58        }
59        return results; // Return the results
60    }
61}
62
1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Trie {
7private:
8    const int inf = 1 << 30;  // Define a large value for comparison purposes
9    Trie* children[26];       // Array to store references to children nodes for 26 letters
10    int length = inf;         // Variable to store the minimum length of a word in the Trie
11    int idx = inf;            // Variable to store the index of the word in the Trie
12
13public:
14    Trie() {
15        for (int i = 0; i < 26; ++i) {
16            children[i] = nullptr;  // Initialize all children to nullptr
17        }
18    }
19
20    // Method to insert a word into the Trie
21    void insert(string word, int index) {
22        Trie* node = this;
23        // Update the root node's length and index if the new word is shorter
24        if (node->length > word.length()) {
25            node->length = word.length();
26            node->idx = index;
27        }
28        // Traverse the word from end to start
29        for (int k = word.length() - 1; k >= 0; --k) {
30            int charIdx = word[k] - 'a';  // Compute the index for the character
31            // Create a new Trie node if there's no child for this character
32            if (node->children[charIdx] == nullptr) {
33                node->children[charIdx] = new Trie();
34            }
35            node = node->children[charIdx];  // Move to the child node
36            // Update the node's length and index if the new word is shorter
37            if (node->length > word.length()) {
38                node->length = word.length();
39                node->idx = index;
40            }
41        }
42    }
43
44    // Method to query and find the index of the shortest matching suffix in the Trie
45    int query(string word) {
46        Trie* node = this;
47        // Traverse the word from end to start
48        for (int k = word.length() - 1; k >= 0; --k) {
49            int charIdx = word[k] - 'a';  // Compute the index for the character
50            // Break if no matching child is found
51            if (node->children[charIdx] == nullptr) {
52                break;
53            }
54            node = node->children[charIdx];  // Move to the child node
55        }
56        return node->idx;  // Return the index of the shortest matching suffix
57    }
58};
59
60class Solution {
61public:
62    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
63        Trie* trie = new Trie();  // Create a new Trie instance
64        // Insert each word from wordsContainer into the Trie
65        for (int i = 0; i < wordsContainer.size(); ++i) {
66            trie->insert(wordsContainer[i], i);
67        }
68        int n = wordsQuery.size();  // Get the number of query words
69        vector<int> result(n);  // Initialize result vector to store indices
70        // Query each word from wordsQuery against the Trie
71        for (int i = 0; i < n; ++i) {
72            result[i] = trie->query(wordsQuery[i]);
73        }
74        return result;  // Return the result vector
75    }
76};
77
1// Define the Trie data structure using arrays to hold child nodes.
2let children: Trie[] = new Array<Trie>(26).fill(null);
3let length: number = Infinity;
4let idx: number = Infinity;
5
6// Insert a word into the Trie with tracking its index.
7function insert(w: string, i: number): void {
8    let node: { children: Trie[], length: number, idx: number } = { children, length, idx };
9
10    // If the current node's shortest word isn't better than the current word, update it.
11    if (node.length > w.length) {
12        node.length = w.length;
13        node.idx = i;
14    }
15
16    // Insert characters of the word into the Trie, starting from the end.
17    for (let k: number = w.length - 1; k >= 0; --k) {
18        let charIndex: number = w.charCodeAt(k) - 'a'.charCodeAt(0);
19
20        // If a child doesn't exist for this character, create a new Trie node.
21        if (node.children[charIndex] == null) {
22            node.children[charIndex] = { children: new Array<Trie>(26).fill(null), length: Infinity, idx: Infinity };
23        }
24
25        // Move to the child node.
26        node = node.children[charIndex];
27
28        // Update the length and index if this node represents a shorter word.
29        if (node.length > w.length) {
30            node.length = w.length;
31            node.idx = i;
32        }
33    }
34}
35
36// Query the Trie to find the index of the shortest word with a common suffix.
37function query(w: string): number {
38    let node: { children: Trie[], length: number, idx: number } = { children, length, idx };
39
40    // Traverse the Trie from the end of the query word.
41    for (let k: number = w.length - 1; k >= 0; --k) {
42        let charIndex: number = w.charCodeAt(k) - 'a'.charCodeAt(0);
43
44        // Break if no child exists for the current character.
45        if (node.children[charIndex] == null) {
46            break;
47        }
48        node = node.children[charIndex];
49    }
50
51    // Return the index of the word found.
52    return node.idx;
53}
54
55// Function to find indices of the shortest words with a common suffix for a list of queries.
56function stringIndices(wordsContainer: string[], wordsQuery: string[]): number[] {
57    // Create a new Trie.
58    children = new Array<Trie>(26).fill(null);
59    length = Infinity;
60    idx = Infinity;
61
62    // Insert each word in the wordsContainer array into the Trie.
63    for (let i: number = 0; i < wordsContainer.length; ++i) {
64        insert(wordsContainer[i], i);
65    }
66
67    // Array to hold the results for each word query.
68    const n: number = wordsQuery.length;
69    const ans: number[] = new Array<number>(n);
70
71    // Query the Trie for each word in wordsQuery and store the result.
72    for (let i: number = 0; i < n; ++i) {
73        ans[i] = query(wordsQuery[i]);
74    }
75
76    // Return the resulting indices.
77    return ans;
78}
79

Time and Space Complexity

The time complexity of the code is O(L_1 ร— |ฮฃ| + L_2), where L_1 is the sum of the lengths of the strings in wordsContainer, L_2 is the sum of the lengths of the strings in wordsQuery, and |ฮฃ| = 26, the size of the character set (for lowercase English letters).

The space complexity is O(L_1 ร— |ฮฃ|), where L_1 is the sum of the lengths of the strings in wordsContainer, and |ฮฃ| = 26 because each node in the Trie can have up to 26 children.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Donโ€™t Miss This!

Load More