forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWordFilter.java
More file actions
124 lines (108 loc) · 3.76 KB
/
WordFilter.java
File metadata and controls
124 lines (108 loc) · 3.76 KB
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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.
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.
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.
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;
}
}
}