[link](https://leetcode.com/problems/prefix-and-suffix-search/)

---

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.

---

TrieNode:
The TrieNode represents a single node in the Trie data structure. It has the following attributes:

children: A dictionary that maps characters to their corresponding child nodes. This allows quick access to child nodes based on the characters in the words.
index: An integer that stores the index of a word that ends at this node. If index is not -1, it means that a word ends at this node, and index represents the index of that word in the list of words.
Trie:
The Trie class is responsible for managing the Trie data structure. It has the following methods:

addWord: This method takes a word and its index as input and adds the word to the Trie. It iterates through each character in the word, creating new TrieNode objects as needed. It updates the index attribute of the last node to store the index of the word that ends at that node.

searchWord: This method takes a prefix and suffix as input and searches for a word with the given prefix and suffix in the Trie. To find the word efficiently, it concatenates the prefix and suffix with '#' in between to form the search word. It then traverses the Trie based on the characters in the search word. If the search word is present in the Trie, it returns the index stored at the last node; otherwise, it returns -1.

WordFilter:
The WordFilter class uses the Trie to store and search for words with a given prefix and suffix. It has the following methods:

__init__: The constructor initializes the Trie object and inserts all the words in the input list into the Trie. For each word, it concatenates the word with itself (separated by '#') to handle suffixes. Then, it inserts all possible suffixes of the word into the Trie with the corresponding index. This ensures that the Trie contains all possible words with different prefixes and suffixes.

f: This method performs the query for a word with the given prefix and suffix. It constructs the search word by concatenating the prefix and suffix with '#' in between. Then, it calls the searchWord method of the Trie to find the word efficiently. If the word is found in the Trie, the method returns the index of the word; otherwise, it returns -1.

#### Solution 1

class TrieNode():

    def __init__(self):
        self.children = {}
        self.index = -1


class Trie():
    
    def __init__(self):
        self.root = TrieNode()

    
    def addWord(self, word, index):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
            curr.index = index

    
    def searchWord(self, prefix, suffix):
        curr = self.root
        word = suffix + "#" + prefix
        for c in word:
            if c not in curr.children:
                return -1
            curr = curr.children[c]
        return curr.index


class WordFilter:

    def __init__(self, words: List[str]):
        self.T = Trie()
        for i, word in enumerate(words):
            N = len(word)
            trieWord = word + "#" + word
            for j in range(N):
                self.T.addWord(trieWord[j:], i)


    def f(self, pref: str, suff: str) -> int:
        return self.T.searchWord(pref, suff)
        

The time complexity for constructing the Trie is O(N * m^2), where N is the number of words and m is the average length of a word. The time complexity for querying is O(m), where m is the combined length of the prefix and suffix.

The space complexity is O(N * m^2) to store the Trie, where N is the number of words, and m is the average length of a word.