745. Prefix and Suffix Search

Problem Description

The problem requires the design of a specialized dictionary that allows for searching words by both a prefix and a suffix. Here's how the class should work:

• The WordFilter class should be initialized with an array of words. These are the words that are going to be added to the dictionary.
• The class should have a function f(pref, suff) that, given a prefix pref and a suffix suff, returns the highest index of any word that starts with pref and ends with suff. If there are no words that meet these criteria, the function should return -1.

This problem is about efficiently managing a set of strings so that they can be queried by their prefixes and suffixes. Implementing such a structure with fast lookup speeds can be challenging due to the complexity of string comparisons in a potentially large dataset.

Intuition

To solve this problem, we can take advantage of a [trie](https://en.wikipedia.org/wiki/Trie), which is a tree-like data structure that stores a dynamic set of strings in a way that makes it easy to retrieve all the keys with a common prefix. For this problem, we actually need two tries: one for prefixes and one for suffixes. Here's why this approach is effective:

• By inserting each word into the prefix trie normally, and into the suffix trie in reversed order, we efficiently prepare the data for the specific queries we're about to receive.
• Each node in the trie keeps a list of all the indexes of the words that pass through that node, which allows us to find all the words that have a specific prefix or suffix.
• Upon querying, we look up the prefix in the prefix trie to get a list of word indexes with that prefix, and we look up the reversed suffix in the suffix trie to get a list of word indexes with that suffix.
• Once we have both lists of indexes for a given prefix and suffix, we start from the end of each list (since we want the largest index) and compare the indexes. We step backwards through the lists, looking for a match. Because both lists are sorted, we are able to efficiently find the greatest index that appears in both lists, or decide that no such index exists if we reach the beginning of either list.

Given that we are dealing with words which are essentially sequences of characters, a trie allows us to narrow down our search space as we progress each character further into the word, making it a suitable data structure for both time and space efficiency in this scenario.

Learn more about Trie patterns.

Solution Approach

The solution approach involves the construction and utilization of two trie data structures:

• Prefix Trie (self.p): This trie stores all the words of the dictionary by their prefix. When a word is inserted, each character of the word is traversed, creating a tree pathway if it doesn't already exist. At every node, the index of the word in the original dictionary is appended to the indexes list. This enables the trie to keep track of all the dictionary indexes that share the same prefix up to that point.

• Suffix Trie (self.s): The suffix trie holds the words in reversed order to facilitate suffix searching. The process of insertion is similar to the prefix trie, except that the word is inserted backwards. Thus, when searching for a particular suffix, we search the trie with the reversed suffix.

Both tries are filled with each word's respective prefixes and reversed suffixes, along with their dictionary index. When performing a lookup with the f function:

1. We first search the prefix trie with the given prefix, pref. This results in a list of indexes, a, containing all the words that start with that prefix.

2. Similarly, we search the suffix trie with the reversed suffix, suff[::-1]. This yields a list of indexes, b, containing all the words that end with the specified suffix.

3. With both lists a and b, we now need to find the largest index that is common to both. Since the indexes are stored in ascending order within the trie, we compare a and b's values starting from their ends (the largest indexes).

4. We iterate backwards through both lists simultaneously comparing their elements:

   • If the indexes at our current pointers match (a[i] == b[j]), we've found the highest index of a word that satisfies both the prefix and suffix requirements. We return this index.

   • If a[i] is larger than b[j], we decrement i because we need to find a smaller index in a that might match an index in b.

   • Conversely, if b[j] is larger than a[i], we decrement j to try and find a smaller index in b that matches an index in a.

5. The iteration continues until either list has been fully traversed (indicated by ~i or ~j becoming False when the pointers become negative). If we haven't found a matching index by this point, we return -1.

The clever use of tries allows us to optimize the lookup times for both prefixes and suffixes. Moreover, by keeping track of the indexes at each node of the trie, the solution enables an efficient way to determine the highest index where the prefix and suffix conditions overlap. This approach significantly reduces the complexity compared to brute force methods which would otherwise involve comparing each possible prefix and suffix pair in the dictionary.

Example Walkthrough

Let's go through an example to illustrate the solution approach using two words: "apple" and "apply". These words will be used to initialize our WordFilter class.

1. Initializing WordFilter: We create a WordFilter object and pass the words ["apple", "apply"] to the constructor.

2. Building Prefix Trie (self.p): Here is a simplified visual of the prefix trie after inserting "apple" and "apply":

   1root
   2 | 
   3 a
   4 |
   5 p
   6/ \

p l | | l y |
e

1As each word is inserted, each character forms a path in the trie if it doesn't exist already. The index of the word is stored at the end of the path for that word. The prefix trie would have the indices of the words as they appear in the list: index 0 for "apple" and index 1 for "apply".
2
33. **Building Suffix Trie (`self.s`):** The suffix trie looks different, as it is constructed using the reversed words. After inserting the reversed words "elppa" and "ylppa", it will look like:

root | a | p /
p l | | l e |
y

1Like the prefix trie, the indices are kept at the end of each path - index 0 for "apple" and index 1 for "apply".
2
34. **Querying with `f` Function:** Suppose we want to find a word that has the prefix "ap" and the suffix "le". We call `f("ap", "le")`.
4
55. **Search the Prefix Trie:** We search for "ap" in the prefix trie (`self.p`). This gives us the list `[0, 1]` since both "apple" and "apply" have the prefix "ap".
6
76. **Search the Suffix Trie:** Now, we look up the reversed suffix "le" which becomes "el" in the suffix trie (`self.s`). The list obtained here is `[0]` because only "apple" has the suffix "le".
8
97. **Find Largest Common Index:** We look for the largest index that is common between the two lists:
10- The list from the prefix trie is `[0, 1]`.
11- The list from the suffix trie is `[0]`.
12
13We compare from the ends, but since both lists contain the index `0` and that is the largest value in the suffix list, we return it. Hence, `f("ap", "le")` returns `0`, indicating "apple" is the word that matches these criteria with the highest index.
14
15This approach quickly finds the highest index common to both the specified prefix and suffix without the need to compare each word in the dictionary. It efficiently narrows down the search space and leads to significant time savings, especially when dealing with a large number of queries or a large dictionary.

Solution Implementation

Time and Space Complexity

Time Complexity:

1. Trie Construction: - O(m * n), where m is the average length of the words, and n is the total number of words. We process each word letter by letter and at each letter of each word, we may potentially create a new Trie node.

2. WordFilter Constructor: - O(m * n). The constructor itself calls the insert method of the Trie class for each word and its reverse once, which is 2 * m * n.

3. insert method: - O(m). We need to traverse or create Trie nodes for each character in the word and push the index into indexes array which can take up to O(m) operations where m is the length of the word.

4. search method: - O(m + k), where k is the number of entries in the index list. For each character in the prefix or suffix, we traverse the Trie, and then we traverse the list of indexes at the final Trie node.

5. f function: It depends on how many indexes are there to process. If the lengths of both lists are a_i and b_i for prefix and suffix respectively, then the complexity is - O(a_i + b_i), as we are iterating through both lists at most once. In the worst case scenario, it could be - O(n), where n is the total number of words since every single word could potentially match the prefix or suffix.

Space Complexity:

1. Trie Storage: - O(26 * m * n), each node could potentially have up to 26 children and we could have a unique path for every single letter in every word. However, due to common prefixes, the space complexity might be less in practice.

2. indexes Arrays Storage: - O(n * m), each index could be stored in the list of potentially every node in the path of a word in the worst case, where m is the average length of the words and n is the number of words.

Overall, for the WordFilter data structure, the space complexity can still be approximated as - O(26 * m * n) due to the Trie nodes being the dominating factor.

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