-
Notifications
You must be signed in to change notification settings - Fork 81
/
ImplementMagicDictionary676.java
176 lines (151 loc) 路 5.53 KB
/
ImplementMagicDictionary676.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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/**
* Implement a magic directory with buildDict, and search methods.
*
* For the method buildDict, you'll be given a list of non-repetitive words to
* build a dictionary.
*
* For the method search, you'll be given a word, and judge whether if you
* modify exactly one character into another character in this word, the
* modified word is in the dictionary you just built.
*
* Example 1:
* Input: buildDict(["hello", "leetcode"]), Output: Null
* Input: search("hello"), Output: False
* Input: search("hhllo"), Output: True
* Input: search("hell"), Output: False
* Input: search("leetcoded"), Output: False
*
* Note:
* You may assume that all the inputs are consist of lowercase letters a-z.
* For contest purpose, the test data is rather small by now. You could think
* about highly efficient algorithm after the contest.
* Please remember to RESET your class variables declared in class
* MagicDictionary, as static/class variables are persisted across multiple
* test cases. Please see here for more details.
*/
public class ImplementMagicDictionary676 {
class MagicDictionary {
private Trie trie = new Trie();
/** Initialize your data structure here. */
public MagicDictionary() {
}
/** Build a dictionary through a list of words */
public void buildDict(String[] dict) {
for (String word: dict) {
trie.add(word);
}
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
public boolean search(String word) {
return trie.search(word);
}
class Trie {
Trie[] children = new Trie[26];
boolean isWord;
void add(String word) {
if (word == null || word.length() == 0) return;
add(word.toCharArray(), 0);
}
void add(char[] word, int i) {
if (word.length == i) {
isWord = true;
return;
}
if (children[word[i]-'a'] == null) {
children[word[i]-'a'] = new Trie();
}
children[word[i]-'a'].add(word, i+1);
}
boolean search(String word) {
if (word == null) return false;
return search(word.toCharArray(), 0, false);
}
boolean search(char[] word, int start, boolean modified) {
if (word.length == start) {
return modified && isWord;
}
for (int i=0; i<26; i++) {
if (children[i] == null) continue;
if (word[start] == (i + 'a')) {
if (children[i].search(word, start+1, modified)) return true;
} else {
if (modified) continue;
if (children[i].search(word, start+1, true)) return true;
}
}
return false;
}
}
}
/**
* https://leetcode.com/problems/implement-magic-dictionary/solution/
*/
class MagicDictionary2 {
Map<Integer, ArrayList<String>> buckets;
public MagicDictionary() {
buckets = new HashMap();
}
public void buildDict(String[] words) {
for (String word: words) {
buckets.computeIfAbsent(word.length(), x -> new ArrayList()).add(word);
}
}
public boolean search(String word) {
if (!buckets.containsKey(word.length())) return false;
for (String candidate: buckets.get(word.length())) {
int mismatch = 0;
for (int i = 0; i < word.length(); ++i) {
if (word.charAt(i) != candidate.charAt(i)) {
if (++mismatch > 1) break;
}
}
if (mismatch == 1) return true;
}
return false;
}
}
/**
* https://leetcode.com/problems/implement-magic-dictionary/solution/
*/
public class MagicDictionary3 {
Set<String> words;
Map<String, Integer> count;
public MagicDictionary() {
words = new HashSet();
count = new HashMap();
}
private ArrayList<String> generalizedNeighbors(String word) {
ArrayList<String> ans = new ArrayList();
char[] ca = word.toCharArray();
for (int i = 0; i < word.length(); ++i) {
char letter = ca[i];
ca[i] = '*';
String magic = new String(ca);
ans.add(magic);
ca[i] = letter;
}
return ans;
}
public void buildDict(String[] words) {
for (String word: words) {
this.words.add(word);
for (String nei: generalizedNeighbors(word)) {
count.put(nei, count.getOrDefault(nei, 0) + 1);
}
}
}
public boolean search(String word) {
for (String nei: generalizedNeighbors(word)) {
int c = count.getOrDefault(nei, 0);
if (c > 1 || c == 1 && !words.contains(word)) return true;
}
return false;
}
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary obj = new MagicDictionary();
* obj.buildDict(dict);
* boolean param_2 = obj.search(word);
*/
}