Solution: Prefix and Suffix Search
Tags: algorithms, javascript, java, python
Published: 2021-05-01 16:13:45

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/prefix-and-suffix-search/discuss/1185480).*

---

#### [Leetcode Problem #745 (*Hard*): Prefix and Suffix Search](https://leetcode.com/problems/prefix-and-suffix-search/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Design a special dictionary which has some words and allows you to search 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 prefix, string suffix)` Returns the index of the word in the dictionary which has the prefix `prefix` and the suffix `suffix`. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return `-1`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|["WordFilter", "f"]<br>[[["apple"]], ["a", "e"]]
Output:|[null, 0]
Explanation:|WordFilter wordFilter = new WordFilter(["apple"]);<br>wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = 'e".

---

#### ***Constraints:***
>
 - `1 <= words.length <= 15000`
 - `1 <= words[i].length <= 10`
 - `1 <= prefix.length, suffix.length <= 10`
 - `words[i]`, `prefix` and `suffix` consist of lower-case English letters only.
 - At most `15000` calls will be made to the function `f`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

Whenever we have to deal with searching for data using a prefix or a suffix, this naturally points to a **trie** solution. A trie is a type of data structure that uses a branching tree format where the nodes represent segments of data (usually characters) to make searching by prefix faster and easier.

The difficulty in this case is that we're searching by both prefix and suffix, so we can create two trie structures, one for prefixes and one for suffixes (**pTrie, sTrie**). Then we can iterate through **words** and **insert()** each word into the two tries.

To do so, we'll iterate through the characters of the word, forwards for **pTrie** and backwards for **sTrie**, and move from node to node as the word moves from character to character. At each node, we'll update the **vals** array with the current **index**. The **vals** array represents the indices of all the words that run through the current node. Since we're iterating through **words** in **index** order, each node's **vals** array will be sorted in **index** order, as well.

For our find method, **f()**, we'll be doing the same in reverse. We'll navigate separately through **pTrie** with **pre** and **sTrie** with **suf** to find the **vals** arrays containing the indices of each word that matches those prefixes and suffixes. If at any point a particular trie does not have the next character, we can **return -1**.

Once we've successfully obtained the two **vals** arrays (**pVals, sVals**), we can cross-reference their contents, starting at the end, and look for the largest index that occurs in both. If we find one, we can **return** it, otherwise we can **return -1**.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
class WordFilter {
    constructor(words) {
        this.pTrie = new Array(27)
        this.sTrie = new Array(27)
        for (let index = 0; index < words.length; index++) {
            let word = words[index], wlen = word.length
            this.insert(word, index, this.pTrie, 0, wlen, 1)
            this.insert(word, index, this.sTrie, wlen-1, -1, -1)
        }
    }
    
    insert(word, index, trie, start, end, step) {
        for (let i = start; i != end; i += step) {
            let c = word.charCodeAt(i) - 97
            if (!trie[c]) trie[c] = new Array(27)
            trie = trie[c]
            if (!trie[26]) trie[26] = []
            trie[26].push(index)
        }
    }
    
    retrieve(word, trie, start, end, step) {
        for (let i = start; i != end; i += step) {
            let c = word.charCodeAt(i) - 97
            if (!trie[c]) return -1
            trie = trie[c]
        }
        return trie[26]
    }
    
    f(pre, suf) {
        let pVals = this.retrieve(pre, this.pTrie, 0, pre.length, 1),
            sVals = this.retrieve(suf, this.sTrie, suf.length-1, -1, -1),
            svix = sVals.length - 1, pvix = pVals.length - 1
        while (~svix && ~pvix) {
            let sVal = sVals[svix], pVal = pVals[pvix]
            if (sVal === pVal) return sVal
            sVal > pVal ? svix-- : pvix--
        }
        return -1
    }
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class WordFilter:
    def __init__(self, words: List[str]):
        self.pTrie = [None] * 27
        self.sTrie = [None] * 27
        for index in range(len(words)):
            self.insert(words[index], index, self.pTrie)
            self.insert(words[index][::-1], index, self.sTrie)
            
    def insert(self, word: str, index: int, trie: dict):
        for c in word:
            cval = ord(c) - 97
            if not trie[cval]: trie[cval] = [None] * 27
            trie = trie[cval]
            if not trie[26]: trie[26] = []
            trie[26].append(index)
            
    def retrieve(self, word: str, trie: dict) -> list:
        for c in word:
            cval = ord(c) - 97
            trie = trie[cval]
            if not trie: return []
        return trie[26]

    def f(self, pre: str, suf: str) -> int:
        pVals = self.retrieve(pre, self.pTrie)
        sVals = self.retrieve(suf[::-1], self.sTrie)
        svix, pvix = len(sVals) - 1, len(pVals) - 1
        while ~svix and ~pvix:
            sVal, pVal = sVals[svix], pVals[pvix]
            if sVal == pVal: return sVal
            if sVal > pVal: svix -= 1
            else: pvix -= 1
        return -1
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public List<Integer> vals = new ArrayList<>();
}

class WordFilter {
    private TrieNode pTrie = new TrieNode();
    private TrieNode sTrie = new TrieNode();
    
    public WordFilter(String[] words) {
        for (int index = 0; index < words.length; index++) {
            char[] word = words[index].toCharArray();
            int wlen = word.length;
            insert(word, index, pTrie, 0, wlen, 1);
            insert(word, index, sTrie, wlen-1, -1, -1);
        }
    }
            
    private void insert(char[] word, int index, TrieNode trie, int start, int end, int step) {
        for (int i = start; i != end; i += step) {
            int c = word[i] - 'a';
            if (trie.children[c] == null)
                trie.children[c] = new TrieNode();
            trie = trie.children[c];
            trie.vals.add(index);
        }
    }
    
    private List<Integer> retrieve(char[] word, TrieNode trie, int start, int end, int step) {
        for (int i = start; i != end; i += step) {
            trie = trie.children[word[i]-'a'];
            if (trie == null) return new ArrayList<>();
        }
        return trie.vals;
    }
    
    public int f(String pre, String suf) {
        List<Integer> pVals = retrieve(pre.toCharArray(), pTrie, 0, pre.length(), 1);
        List<Integer> sVals = retrieve(suf.toCharArray(), sTrie, suf.length()-1, -1, -1);
        int svix = sVals.size() - 1, pvix = pVals.size() - 1;
        while (svix >= 0 && pvix >= 0) {
            int sVal = sVals.get(svix), pVal = pVals.get(pvix);
            if (sVal == pVal) return sVal;
            if (sVal > pVal) svix--;
            else pvix--;
        }
        return -1;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    vector<int> vals;
};

class WordFilter {
private:
    TrieNode *pTrie, *sTrie;
    
public:
    WordFilter(vector<string>& words) {
        pTrie = new TrieNode();
        sTrie = new TrieNode();
        for (int index = 0; index < words.size(); index++) {
            string word = words[index];
            insert(word, index, pTrie);
            reverse(word.begin(), word.end());
            insert(word, index, sTrie);
        }
    }
    
    void insert(string word, int index, TrieNode* trie) {
        for (auto c : word) {
            int cval = c - 'a';
            if (!trie->children[cval])
                trie->children[cval] = new TrieNode();
            trie = trie->children[cval];
            trie->vals.push_back(index);
        }
    }
    
    vector<int>* retrieve(string str, TrieNode* trie) {
        for (auto c : str) {
            trie = trie->children[c-'a'];
            if (!trie) return nullptr;
        }
        return &trie->vals;
    }
    
    int f(string pre, string suf) {
        vector<int>* pVals = retrieve(pre, pTrie);
        reverse(suf.begin(), suf.end());
        vector<int>* sVals = retrieve(suf, sTrie);
        int svix = sVals->size() - 1, pvix = pVals->size() - 1;
        while (~svix && ~pvix) {
            int sVal = (*sVals)[svix], pVal = (*pVals)[pvix];
            if (sVal == pVal) return sVal;
            if (sVal > pVal) svix--;
            else pvix--;
        }
        return -1;
    }
};
```