#745

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Prefix and Suffix Search

Design a dictionary to search words by both prefix and suffix using a Trie structure and hash lookups.

Problem Statement

Given a list of words, the goal is to design a special dictionary that supports two operations: searching for words by prefix and suffix. You need to implement the WordFilter class, which will allow performing these operations efficiently.

To achieve this, the class should support a function f(prefix, suffix) that returns the index of the word in the dictionary that matches both the given prefix and suffix. If no word matches, return -1. The solution should be optimized to handle large inputs and multiple queries.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["WordFilter", "f"] [[["apple"]], ["a", "e"]] Output [null, 0] Explanation WordFilter wordFilter = new WordFilter(["apple"]); wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".

Constraints

1 <= words.length <= 104
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i], pref and suff consist of lowercase English letters only.
At most 104 calls will be made to the function f.

Solution Approach

Trie-based Dictionary with Hashing

The core idea is to use a Trie structure where each word is stored in multiple forms by appending combinations of prefixes and suffixes. By adding entries like 'apple{apple', 'pple{apple', and so on, we can efficiently match words based on prefix and suffix in one pass using hash lookups.

Array Scanning for Prefix and Suffix Matching

Array scanning is employed to generate all possible combinations of prefix-suffix pairs for each word. By scanning through the list and storing these combinations in the Trie, we ensure fast lookups during queries.

Optimized Query Performance with Hash Lookups

The function f(prefix, suffix) should be optimized to leverage the pre-stored hash keys in the Trie. This allows constant time lookups for each query, ensuring that the solution handles up to the maximum query limits efficiently.

Complexity Analysis

Metric	Value
Time	O(NK^2 + QK)
Space	O(NK^2)

The time complexity for the construction of the Trie is O(NK^2), where N is the number of words and K is the maximum word length. Each query takes O(QK), where Q is the number of queries and K is the length of the prefix and suffix. The space complexity is O(NK^2) due to the storage of all prefix-suffix combinations in the Trie.

What Interviewers Usually Probe

The candidate demonstrates understanding of Trie structures and hashing for prefix-suffix matching.
They should consider how to optimize space usage while maintaining efficiency in multiple queries.
Look for attention to detail when managing combinations of prefixes and suffixes in the Trie.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the design by not leveraging the Trie structure effectively.
Failing to optimize for multiple queries by not using hash-based lookups.
Not handling the space complexity efficiently, leading to excessive memory usage.

Follow-up variants

Consider modifying the problem to handle a fixed-size dictionary and optimize for multiple queries using pre-processing techniques.
A variant could involve supporting more complex patterns beyond simple prefix and suffix matching, like substrings.
Handling words with overlapping prefixes and suffixes might require additional data structures or optimizations.

FAQ

What is the best way to design the Trie structure for prefix and suffix matching?

The Trie structure should store each word's prefix-suffix combinations as keys, allowing fast lookups during query operations.

How does the time complexity of this problem scale with multiple queries?

The time complexity scales linearly with the number of queries, each taking O(K) time to match the prefix and suffix.

Can this problem be solved using a hash table alone?

While hash tables can help with lookups, a Trie structure is necessary for efficient prefix and suffix storage, enabling quick matching.

How do we handle large inputs efficiently in this problem?

By pre-processing the word list and storing combinations of prefixes and suffixes in a Trie, we minimize query time and space usage.

How can GhostInterview assist with debugging this problem?

GhostInterview can provide insights on Trie optimizations, help ensure space complexity is controlled, and offer step-by-step solutions for common issues.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class WordFilter:
    def __init__(self, words: List[str]):
        self.d = {}
        for k, w in enumerate(words):
            n = len(w)
            for i in range(n + 1):
                a = w[:i]
                for j in range(n + 1):
                    b = w[j:]
                    self.d[(a, b)] = k

    def f(self, pref: str, suff: str) -> int:
        return self.d.get((pref, suff), -1)


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class WordFilter:
    def __init__(self, words: List[str]):
        self.d = {}
        for k, w in enumerate(words):
            n = len(w)
            for i in range(n + 1):
                a = w[:i]
                for j in range(n + 1):
                    b = w[j:]
                    self.d[(a, b)] = k

    def f(self, pref: str, suff: str) -> int:
        return self.d.get((pref, suff), -1)


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)

Continue Practicing

#720 longest word in dictionary #792 number of matching subsequences #692 top k frequent words