How do you solve Prefix and Suffix Search on LeetCode?

Prefix and Suffix Search (LeetCode #745) 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: Using a Trie allows for efficient prefix and suffix searching.

What is the brute force solution for Prefix and Suffix Search?

The brute force approach for Prefix and Suffix Search is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks each word in the dictionary to see if it matches the given prefix and suffix. This is straightforward but inefficient, especially as the number of words increases. The optimal Optimal Solution approach improves this to O(n + m).

What algorithm or data structure is used to solve Prefix and Suffix Search?

Prefix and Suffix Search uses the following concepts: Array, Hash Table, String, Design, Trie. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Prefix and Suffix Search?

Explain your thought process clearly while coding. Discuss the trade-offs of different approaches. Practice implementing Tries, as they are common in string-related problems.

What are common mistakes when solving Prefix and Suffix Search?

Not considering the case where no matching word exists. Failing to understand how to construct the Trie properly.

#745

Prefix and Suffix Search

Hard

ArrayHash TableStringDesignTrieHash MapArray

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)

The optimal solution uses a Trie data structure to efficiently store and search for words based on prefixes and suffixes. By combining the prefix and suffix into a single search key, we can quickly find the desired word index.

⚙️

Algorithm

3 steps

1Step 1: Create a TrieNode class to represent each node in the Trie.
2Step 2: Insert each word into the Trie by adding all possible combinations of suffixes and their corresponding indices.
3Step 3: When searching, combine the suffix and prefix into a single search key and traverse the Trie to find the maximum index.

solution.py20 lines

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.index = -1
5
6class WordFilter:
7    def __init__(self, words):
8        self.root = TrieNode()
9        for i, word in enumerate(words):
10            for j in range(len(word) + 1):
11                self.root.children.setdefault(word[j:], TrieNode()).index = i
12
13    def f(self, pref, suff):
14        node = self.root
15        search_key = suff + '{'
16        for char in search_key:
17            if char not in node.children:
18                return -1
19            node = node.children[char]
20        return node.index

ℹ

Complexity note: The time complexity is O(n + m), where n is the number of words and m is the length of the prefix and suffix combined. This is efficient because we only traverse the Trie once for each search.

1Using a Trie allows for efficient prefix and suffix searching.
2Combining suffixes with a special character helps in managing the search space.

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