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.
**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.
To efficiently answer prefix and suffix queries, we can preprocess all possible prefix and suffix combinations for each word and store their largest index in a hash map. This allows for constant time lookups during queries.
classWordFilter {
Map<String, Integer> mp =new HashMap<>();
publicWordFilter(String[] words) {
for (int i = 0; i < words.length; ++i) {
String w = words[i];
for (int p = 1; p <= w.length(); ++p) {
String pref = w.substring(0, p);
for (int s = 0; s <= w.length(); ++s) {
String suff = w.substring(w.length() - s);
mp.put(pref +"#"+ suff, i);
}
}
}
}
publicintf(String pref, String suff) {
String key = pref +"#"+ suff;
return mp.getOrDefault(key, -1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classWordFilter(words: Array<String>) {
privateval mp = mutableMapOf<String, Int>()
init {
for ((i, w) in words.withIndex()) {
for (p in1..w.length) {
val pref = w.substring(0, p)
for (s in0..w.length) {
val suff = w.substring(w.length - s)
mp["$pref#$suff"] = i
}
}
}
}
funf(pref: String, suff: String): Int = mp["$pref#$suff"] ?: -1}
1
2
3
4
5
6
7
8
9
10
11
classWordFilter:
def__init__(self, words: list[str]) ->None:
self.mp: dict[str, int] = {}
for i, w in enumerate(words):
for p in range(1, len(w)+1):
pref = w[:p]
for s in range(len(w)+1):
suff = w[len(w)-s:]
self.mp[f"{pref}#{suff}"] = i
deff(self, pref: str, suff: str) -> int:
return self.mp.get(f"{pref}#{suff}", -1)
⏰ Time complexity: O(N * L^2) for preprocessing, where N is number of words and L is max word length. Each word generates O(L^2) prefix-suffix pairs. Query is O(1).
🧺 Space complexity: O(N * L^2), storing all prefix-suffix pairs for all words.