How do you solve Longest Common Suffix Queries on LeetCode?

Longest Common Suffix Queries (LeetCode #3093) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + m) time complexity and O(n) space complexity. Key insight: Reversing strings simplifies the problem to finding prefixes.

What is the brute force solution for Longest Common Suffix Queries?

The brute force approach for Longest Common Suffix Queries is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will compare each string in wordsQuery with every string in wordsContainer to find the longest common suffix. This is straightforward but inefficient, as it checks all combinations. The optimal Optimal Solution approach improves this to O(n + m).

What algorithm or data structure is used to solve Longest Common Suffix Queries?

Longest Common Suffix Queries uses the following concepts: Array, String, Trie. The recommended patterns to study are: Trie, String Manipulation.

What are the interview tips for Longest Common Suffix Queries?

Explain your thought process clearly while coding. Consider different data structures and their trade-offs. Practice explaining your code to someone else.

What are common mistakes when solving Longest Common Suffix Queries?

Not considering edge cases like empty strings. Forgetting to reverse strings before comparison.

#3093

Longest Common Suffix Queries

Hard

ArrayStringTrieTrieString Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + m)
Space	O(1)	O(n)

💡

Intuition

Time O(n + m)Space O(n)

By reversing the strings, we can transform the problem into finding the longest common prefix. This allows us to use a Trie data structure to efficiently store and retrieve the best matches based on our criteria.

⚙️

Algorithm

4 steps

1Step 1: Reverse all strings in wordsContainer and insert them into a Trie, storing the index of the string at each node.
2Step 2: For each word in wordsQuery, reverse it and traverse the Trie to find the longest common prefix.
3Step 3: During traversal, keep track of the best index based on the criteria (longest prefix, smallest length, earliest occurrence).
4Step 4: Store the best index for each query in the result array.

solution.py38 lines

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.index = -1
5
6class Trie:
7    def __init__(self):
8        self.root = TrieNode()
9
10    def insert(self, word, index):
11        node = self.root
12        for char in word:
13            if char not in node.children:
14                node.children[char] = TrieNode()
15            node = node.children[char]
16            node.index = index
17
18    def search_best(self, word):
19        node = self.root
20        best_index = -1
21        for char in word:
22            if char in node.children:
23                node = node.children[char]
24                best_index = node.index
25            else:
26                break
27        return best_index
28
29def longestCommonSuffix(wordsContainer, wordsQuery):
30    trie = Trie()
31    for index, word in enumerate(wordsContainer):
32        trie.insert(word[::-1], index)
33
34    ans = []
35    for query in wordsQuery:
36        best_index = trie.search_best(query[::-1])
37        ans.append(best_index)
38    return ans

ℹ

Complexity note: The complexity is linear because we only traverse each string once for insertion into the Trie and once for searching, making it efficient.

1Reversing strings simplifies the problem to finding prefixes.
2Using a Trie allows for efficient storage and retrieval based on common characters.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.