# Prefix and Suffix Search
**Difficulty:** HARD
[External](https://leetcode.com/problems/prefix-and-suffix-search)
Canonical: https://scaleengineer.com/dsa/problems/prefix-and-suffix-search
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the `WordFilter` class:

* `WordFilter(string[] words)` Initializes the object with the `words` in the dictionary.
* `f(string pref, string suff)` Returns _the index of the word in the dictionary,_ which has the prefix `pref` and the suffix `suff`. If there is more than one valid index, return **the largest** of them. If there is no such word in the dictionary, return `-1`.

**Example 1:**

**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`.

# Approaches
## Brute Force by Iterating Through Words
This is a straightforward brute-force approach. The constructor does minimal work, simply storing the list of words. For each query to the `f` function, we iterate through the entire list of words to find one that matches the given prefix and suffix.
**Time:** Constructor: O(1).
`f` method: O(N * L) for each call, where N is the number of words and L is the maximum length of a word. The string matching operations `startsWith` and `endsWith` can take up to O(L) time. For Q queries, the total time complexity is O(Q * N * L). · **Space:** O(N * L), where N is the number of words and L is the maximum length of a word. This space is used to store the dictionary of words itself.
**Pros:** Simple to understand and implement.; Low memory overhead, as it only stores the original list of words.
**Cons:** Very slow for a large number of queries, as each query requires a full scan of the dictionary.; Likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The `WordFilter` constructor initializes the object by storing the input array of words. The main logic resides in the `f(pref, suff)` method. This method iterates through the `words` array in reverse order, from the last element to the first. We iterate backwards because the problem requires us to return the largest index if multiple words match. For each word, we check two conditions: if it starts with the given `pref` and if it ends with the given `suff`. The built-in `startsWith()` and `endsWith()` string methods are used for this. The first word (while iterating backwards) that satisfies both conditions is the desired answer, and its index is returned immediately. If the loop finishes without finding any such word, it implies no word in the dictionary meets the criteria, and we return -1.

```java
class WordFilter {
    String[] words;

    public WordFilter(String[] words) {
        this.words = words;
    }

    public int f(String pref, String suff) {
        for (int i = words.length - 1; i >= 0; i--) {
            if (words[i].startsWith(pref) && words[i].endsWith(suff)) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- In the `WordFilter` constructor, store the input `words` array.
- In the `f(pref, suff)` method, iterate through the `words` array from the last index (`words.length - 1`) down to `0`.
- For each `word` at index `i`:
  - Use string functions to check if `word.startsWith(pref)` and `word.endsWith(suff)`.
  - If both conditions are true, it means we've found a match. Since we are iterating backwards, this is the match with the largest index. Return `i` immediately.
- If the loop completes without finding any matches, return `-1`.

## Trie of Suffix Wrapped Words
This efficient approach involves significant pre-processing during initialization to make subsequent queries very fast. We build a single, specialized Trie data structure that cleverly encodes both suffix and prefix information. For each word, we generate multiple entries to insert into the Trie, each combining a suffix of the word with the word itself. This allows us to search for a prefix and a suffix simultaneously by querying the Trie with a single, specially constructed key.
**Time:** Constructor: O(N * L^2), where N is the number of words and L is the maximum word length. For each of the N words, we generate O(L) keys, and inserting each key of length O(L) takes O(L) time.
`f` method: O(P + S), where P is the length of the prefix and S is the length of the suffix. This is bounded by O(L), making queries very fast. · **Space:** O(N * L^2), where N is the number of words and L is the maximum word length. The number of nodes in the Trie is bounded by the total number of characters in all the keys we insert. For each of the N words, we insert L+1 keys, and the total length of these keys for a single word is O(L^2).
**Pros:** Extremely fast query time, making it ideal for scenarios with many queries.; The pre-computation in the constructor is a one-time cost.; It's a very elegant solution that fits the problem constraints perfectly.
**Cons:** The constructor can be slow and memory-intensive if the number of words or their lengths are very large.; More complex to implement compared to the brute-force approach.
### Explanation
The core idea is to transform the two-dimensional search (prefix and suffix) into a one-dimensional prefix search, which is what Tries excel at. We achieve this by creating composite keys.

For each word `w` at index `i`, we generate all its suffixes. For every `suffix`, we form a new string `suffix + "#" + w`, where `#` is a separator character that doesn't appear in the words. We insert all these generated strings into a single Trie. Each node in our Trie stores an `index`. When we insert a key corresponding to `words[i]`, we update the `index` at every node along the insertion path to `i`. Because we iterate through the words from index 0 to `n-1`, any node's `index` will be overwritten with progressively larger values, automatically ensuring it holds the largest index of a word that has passed through it.

To query for a `pref` and `suff`, we construct a search key `suff + "#" + pref`. We then traverse the Trie with this key. If a path for this key exists, the node at the end of the path represents all words that have `suff` as a suffix and `pref` as a prefix. The `index` stored at this node will be the largest index of such a word, which is exactly what we need. If the path doesn't exist, no word matches, and we return -1.

```java
class WordFilter {
    private static class TrieNode {
        TrieNode[] children;
        int index;

        TrieNode() {
            // Using '{' as separator, which is 'z' + 1 in ASCII
            children = new TrieNode[27]; 
            index = -1;
        }
    }

    private final TrieNode root;

    public WordFilter(String[] words) {
        root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            // For each suffix of the word...
            for (int j = 0; j <= word.length(); j++) {
                // Create a key like: "suffix{word}"
                String key = word.substring(word.length() - j) + "{" + word;
                insert(key, i);
            }
        }
    }

    private void insert(String key, int index) {
        TrieNode curr = root;
        for (char c : key.toCharArray()) {
            int charIndex = c - 'a';
            if (curr.children[charIndex] == null) {
                curr.children[charIndex] = new TrieNode();
            }
            curr = curr.children[charIndex];
            curr.index = index; // Update index at every node on the path
        }
    }

    public int f(String pref, String suff) {
        // Search for a key like: "suff{pref}"
        String searchKey = suff + "{" + pref;
        TrieNode curr = root;
        for (char c : searchKey.toCharArray()) {
            int charIndex = c - 'a';
            if (curr.children[charIndex] == null) {
                return -1;
            }
            curr = curr.children[charIndex];
        }
        return curr.index;
    }
}
```
### Algorithm
- Define a `TrieNode` class containing an array for child nodes (for 'a'-'z' and a separator character) and an `index` field.
- In the `WordFilter` constructor, initialize a root `TrieNode`.
- Iterate through each `word` at index `i` from `0` to `n-1`.
- For each `word`, generate all its suffixes.
- For each `suffix`, create a special key: `key = suffix + "#" + word` (where '#' is a separator).
- Insert this `key` into the Trie. During insertion, for every node on the path, update its `index` field to `i`. Since we process words in increasing order of their indices, this ensures the `index` field of a node always holds the largest index of a word whose key passes through it.
- In the `f(pref, suff)` method, create a search key: `searchKey = suff + "#" + pref`.
- Traverse the Trie with this `searchKey`. 
- If the path exists, the `index` stored at the final node is the answer.
- If the path breaks at any point, no such word exists, so return `-1`.

# Solutions
### Java

```java
class Trie { Trie [] children = new Trie [ 26 ]; List < Integer > indexes = new ArrayList <>(); void insert ( String word , int i ) { Trie node = this ; for ( char c : word . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; node . indexes . add ( i ); } } List < Integer > search ( String pref ) { Trie node = this ; for ( char c : pref . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { return Collections . emptyList (); } node = node . children [ c ]; } return node . indexes ; } } class WordFilter { private Trie p = new Trie (); private Trie s = new Trie (); public WordFilter ( String [] words ) { for ( int i = 0 ; i < words . length ; ++ i ) { String w = words [ i ]; p . insert ( w , i ); s . insert ( new StringBuilder ( w ). reverse (). toString (), i ); } } public int f ( String pref , String suff ) { suff = new StringBuilder ( suff ). reverse (). toString (); List < Integer > a = p . search ( pref ); List < Integer > b = s . search ( suff ); if ( a . isEmpty () || b . isEmpty ()) { return - 1 ; } int i = a . size () - 1 , j = b . size () - 1 ; while ( i >= 0 && j >= 0 ) { int c = a . get ( i ), d = b . get ( j ); if ( c == d ) { return c ; } if ( c > d ) { -- i ; } else { -- j ; } } return - 1 ; } } /** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(pref,suff); */
```

### CPP

```cpp
class WordFilter { public: unordered_map < string , int > d ; WordFilter ( vector < string >& words ) { for ( int k = 0 ; k < words . size (); ++ k ) { string w = words [ k ]; int n = w . size (); for ( int i = 0 ; i <= n ; ++ i ) { string a = w . substr ( 0 , i ); for ( int j = 0 ; j <= n ; ++ j ) { string b = w . substr ( j , n - j ); d [ a + "." + b ] = k ; } } } } int f ( string pref , string suff ) { string key = pref + "." + suff ; if ( d . count ( key )) return d [ key ]; return - 1 ; } }; /** * Your WordFilter object will be instantiated and called as such: * WordFilter* obj = new WordFilter(words); * int param_1 = obj->f(pref,suff); */
```

### Python

```python
class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . indexes = [] def insert ( self , word , i ): node = self for c in word : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . indexes . append ( i ) def search ( self , pref ): node = self for c in pref : idx = ord ( c ) - ord ( "a" ) if node . children [ idx ] is None : return [] node = node . children [ idx ] return node . indexes class WordFilter : def __init__ ( self , words : List [ str ]): self . p = Trie () self . s = Trie () for i , w in enumerate ( words ): self . p . insert ( w , i ) self . s . insert ( w [:: - 1 ], i ) def f ( self , pref : str , suff : str ) -> int : a = self . p . search ( pref ) b = self . s . search ( suff [:: - 1 ]) if not a or not b : return - 1 i , j = len ( a ) - 1 , len ( b ) - 1 while ~ i and ~ j : if a [ i ] == b [ j ]: return a [ i ] if a [ i ] > b [ j ]: i -= 1 else : j -= 1 return - 1 # Your WordFilter object will be instantiated and called as such: # obj = WordFilter(words) # param_1 = obj.f(pref,suff)
```