/
WordFilter.java
110 lines (98 loc) · 3.38 KB
/
WordFilter.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package design;
import java.util.HashMap;
import java.util.Map;
/**
* Created by gouthamvidyapradhan on 25/12/2017. Given many words, words[i] has weight i.
*
* <p>Design a class WordFilter that supports one function, WordFilter.f(String prefix, String
* suffix). It will return the word with given prefix and suffix with maximum weight. If no word
* exists, return -1.
*
* <p>Examples: Input: WordFilter(["apple"]) WordFilter.f("a", "e") // returns 0 WordFilter.f("b",
* "") // returns -1 Note: words has length in range [1, 15000]. For each test case, up to
* words.length queries WordFilter.f may be made. words[i] has length in range [1, 10]. prefix,
* suffix have lengths in range [0, 10]. words[i] and prefix, suffix queries consist of lowercase
* letters only.
*
* <p>Solution: Implement a trie to store the dictionary of words. For every word insert all the
* possible suffixes into the trie. Additionally overwrite weight each time a word is inserted.
* Example for a word 'cat' all the possible trie insertions are -> #cat, t#cat, at#cat, cat#cat
* Search for 'suffix#prefix' in the trie and return its weight
*/
public class WordFilter {
private Trie trie;
private int maxWeight; // max weight possible
/**
* Main method
*
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
String[] words = {"apple", "cat", "mat", "mars", "abxcd", "abycd", "apple"};
WordFilter wf = new WordFilter(words);
System.out.println(wf.f("abx", ""));
}
public WordFilter(String[] words) {
trie = new Trie();
trie.weight = -1;
maxWeight = words.length - 1;
for (int i = 0; i < words.length; i++) {
String word = words[i];
trie.insert("#" + word, i);
for (int j = 0, l = word.length(); j < l; j++) {
trie.insert(word.substring(j, l) + "#" + word, i);
}
}
}
public int f(String prefix, String suffix) {
if ((suffix == null || suffix.isEmpty()) && (prefix == null || prefix.isEmpty())) {
return maxWeight;
} else if (prefix == null || prefix.isEmpty()) {
return trie.search(suffix + "#");
} else if (suffix == null || suffix.isEmpty()) {
return trie.search("#" + prefix);
} else {
return trie.search(suffix + "#" + prefix);
}
}
public static class Trie {
private Map<Character, Trie> map;
int weight;
/** Initialize your data structure here. */
public Trie() {
map = new HashMap<>();
}
/** Inserts a word into the trie. */
public void insert(String word, int weight) {
if (word != null) {
add(0, word, word.length(), weight);
}
}
private void add(int i, String word, int length, int weight) {
if (i < length) {
char c = word.charAt(i);
map.putIfAbsent(c, new Trie());
Trie subTrie = map.get(c);
subTrie.weight = weight;
subTrie.add(i + 1, word, length, weight);
}
}
/** Returns if the word is in the trie. */
public int search(String word) {
if (word != null) {
return search(0, word, word.length());
}
return -1;
}
private int search(int i, String word, int length) {
if (i < length) {
char c = word.charAt(i);
Trie subTrie = map.get(c);
if (subTrie == null) return -1;
return subTrie.search(i + 1, word, length);
}
return this.weight;
}
}
}