Algorithm

Problem Name: 745. 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`.

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class WordFilter {

private TrieNode root;

public WordFilter(String[] words) {
this.root = new TrieNode();
for (int i = 0; i  <  words.length; i++) {
indexWord(words[i], i);
}
}

public int f(String prefix, String suffix) {
TrieNode curr = root;
for (char c : (suffix + "{" + prefix).toCharArray()) {
if (curr.children[c - 'a'] == null) {
return -1;
}
curr = curr.children[c - 'a'];
}
return curr.maxIdx;
}

private void indexWord(String word, int idx) {
for (int i = word.length() - 1; i >= 0; i--) {
String suffixAndPrefix = word.substring(i, word.length()) + "{" + word;
TrieNode curr = root;
for (char c : suffixAndPrefix.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new TrieNode();
}
curr = curr.children[c - 'a'];
curr.maxIdx = idx;
}
}
}

private class TrieNode {
TrieNode[] children;
int maxIdx;
public TrieNode() {
this.children = new TrieNode[27];
this.maxIdx = 0;
}
}
}
``````
Copy The Code &

Input

cmd
["WordFilter", "f"] [[["apple"]], ["a", "e"]]

Output

cmd
[null, 0]

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const WordFilter = function (words) {
this.trie = new trie()
let val = 0
for (let word of words) {
/* suffix # prefix */
let temp = ''
this.trie.insert('#' + word, val)
this.trie.insert(word + '#', val)
for (let i = 0; i  <  word.length; i++) {
temp = word.substring(i)
temp += '#' + word
this.trie.insert(temp, val)
}
val++
}
}

WordFilter.prototype.f = function (prefix, suffix) {
return this.trie.startsWith(suffix + '#' + prefix)
}

const trie = function () {
this.map = new Map()
this.isEnd = false
this.val = -1
}
trie.prototype.insert = function (word, val) {
let temp = this
let i = 0
while (i < word.length && temp.map.has(word[i])) {
temp.val = Math.max(temp.val, val)
temp = temp.map.get(word[i++])
}
while (i < word.length) {
let t2 = new trie()
temp.map.set(word[i++], t2)
temp.val = Math.max(temp.val, val)
temp = t2
}
temp.isEnd = true
temp.val = Math.max(temp.val, val)
return true
}
trie.prototype.startsWith = function (prefix) {
let temp = this
let i = 0
while (i < prefix.length && temp.map.has(prefix[i]))
temp = temp.map.get(prefix[i++])
return i >= prefix.length ? temp.val : -1
}
``````
Copy The Code &

Input

cmd
["WordFilter", "f"] [[["apple"]], ["a", "e"]]

Output

cmd
[null, 0]

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class WordFilter:
def __init__(self, words):
self.p, self.s, self.ind = collections.defaultdict(set), collections.defaultdict(set), {}
for i, w in enumerate(words):
self.ind[w] = i
for i in range(1, len(w) + 1):
def f(self, prefix, suffix): return max((self.ind[c] for c in self.p[prefix] & self.s[suffix]), default = -1)
``````
Copy The Code &

Input

cmd
["WordFilter", "f"] [[["apple"]], ["a", "e"]]

Output

cmd
[null, 0]