Algorithm
Problem Name: 745. Prefix and Suffix Search
Problem 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 thewordsin the dictionary.f(string pref, string suff)Returns the index of the word in the dictionary, which has the prefixprefand the suffixsuff. 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 <= 1041 <= words[i].length <= 71 <= pref.length, suff.length <= 7words[i],prefandsuffconsist of lowercase English letters only.- At most
104calls will be made to the functionf.
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;
}
}
}
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[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
}
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[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
self.p[""].add(w)
self.s[""].add(w)
for i in range(1, len(w) + 1):
self.p[w[:i]].add(w)
self.s[w[-i:]].add(w)
def f(self, prefix, suffix): return max((self.ind[c] for c in self.p[prefix] & self.s[suffix]), default = -1)
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]