Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit11c6492

Browse files
refactor 211
1 parentbb01f36 commit11c6492

File tree

2 files changed

+94
-59
lines changed

2 files changed

+94
-59
lines changed
Lines changed: 67 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
packagecom.fishercoder.solutions;
22

33
/**
4+
* 211. Add and Search Word - Data structure design
5+
*
46
* Design a data structure that supports the following two operations:
57
68
void addWord(word)
@@ -22,74 +24,80 @@ bool search(word)
2224
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
2325
*/
2426
publicclass_211 {
25-
publicclassWordDictionary {
26-
WordNoderoot =newWordNode();
27+
publicstaticclassSolution1 {
28+
publicstaticclassWordDictionary {
29+
WordNoderoot;
2730

28-
publicvoidaddWord(Stringword) {
29-
char[]chars =word.toCharArray();
30-
addWord(chars,0,root);
31-
}
31+
/** Initialize your data structure here. */
32+
publicWordDictionary() {
33+
root =newWordNode();
34+
}
3235

33-
privatevoidaddWord(char[]chars,intindex,WordNodeparent) {
34-
charc =chars[index];
35-
intidx =c -'a';
36-
WordNodenode =parent.children[idx];
37-
if (node ==null) {
38-
node =newWordNode();
39-
parent.children[idx] =node;
40-
}
41-
if (chars.length ==index +1) {
42-
node.isLeaf =true;
43-
return;
44-
}
45-
addWord(chars, ++index,node);
46-
}
36+
publicvoidaddWord(Stringword) {
37+
char[]chars =word.toCharArray();
38+
addWord(chars,0,root);
39+
}
4740

48-
publicbooleansearch(Stringword) {
49-
returnsearch(word.toCharArray(),0,root);
41+
privatevoidaddWord(char[]chars,intindex,WordNodeparent) {
42+
charc =chars[index];
43+
intidx =c -'a';
44+
WordNodenode =parent.children[idx];
45+
if (node ==null) {
46+
node =newWordNode();
47+
parent.children[idx] =node;
48+
}
49+
if (chars.length ==index +1) {
50+
node.isLeaf =true;
51+
return;
5052
}
53+
addWord(chars, ++index,node);
54+
}
5155

52-
/**This is also a beautifully designed recursive function.*/
53-
privatebooleansearch(char[]chars,intindex,WordNodeparent) {
54-
if (index ==chars.length) {
55-
if (parent.isLeaf) {
56-
returntrue;
57-
}
58-
returnfalse;
59-
}
60-
WordNode[]childNodes =parent.children;
61-
charc =chars[index];
62-
if (c =='.') {
63-
for (inti =0;i <childNodes.length;i++) {
64-
WordNoden =childNodes[i];
65-
if (n !=null) {
66-
booleanb =search(chars,index +1,n);
67-
if (b) {
68-
returntrue;
69-
}
70-
}
71-
}
72-
returnfalse;
73-
}
74-
WordNodenode =childNodes[c -'a'];
75-
if (node ==null) {
76-
returnfalse;
56+
publicbooleansearch(Stringword) {
57+
returnsearch(word.toCharArray(),0,root);
58+
}
59+
60+
/** This is also a beautifully designed recursive function. */
61+
privatebooleansearch(char[]chars,intindex,WordNodeparent) {
62+
if (index ==chars.length) {
63+
if (parent.isLeaf) {
64+
returntrue;
65+
}
66+
returnfalse;
67+
}
68+
WordNode[]childNodes =parent.children;
69+
charc =chars[index];
70+
if (c =='.') {
71+
for (inti =0;i <childNodes.length;i++) {
72+
WordNoden =childNodes[i];
73+
if (n !=null) {
74+
booleanb =search(chars,index +1,n);
75+
if (b) {
76+
returntrue;
77+
}
7778
}
78-
returnsearch(chars, ++index,node);
79+
}
80+
returnfalse;
7981
}
80-
81-
/**This is a cool/standard design for a Trie node class.*/
82-
privateclassWordNode {
83-
booleanisLeaf;
84-
WordNode[]children =newWordNode[26];
82+
WordNodenode =childNodes[c -'a'];
83+
if (node ==null) {
84+
returnfalse;
8585
}
86+
returnsearch(chars, ++index,node);
87+
}
8688

89+
/** This is a cool/standard design for a Trie node class. */
90+
privateclassWordNode {
91+
booleanisLeaf;
92+
WordNode[]children =newWordNode[26];
93+
}
8794
}
8895

89-
/**
90-
* Your WordDictionary object will be instantiated and called as such:
91-
* WordDictionary obj = new WordDictionary();
92-
* obj.addWord(word);
93-
* boolean param_2 = obj.search(word);
94-
*/
96+
/**
97+
* Your WordDictionary object will be instantiated and called as such:
98+
* WordDictionary obj = new WordDictionary();
99+
* obj.addWord(word);
100+
* boolean param_2 = obj.search(word);
101+
*/
102+
}
95103
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._211;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
publicclass_211Test {
10+
privatestatic_211.Solution1.WordDictionarywordDictionarySolution1;
11+
12+
@BeforeClass
13+
publicstaticvoidsetup() {
14+
wordDictionarySolution1 =new_211.Solution1.WordDictionary();
15+
}
16+
17+
@Test
18+
publicvoidtest1() {
19+
wordDictionarySolution1.addWord("bad");
20+
wordDictionarySolution1.addWord("dad");
21+
wordDictionarySolution1.addWord("mad");
22+
assertEquals(false,wordDictionarySolution1.search("pad"));
23+
assertEquals(true,wordDictionarySolution1.search("bad"));
24+
assertEquals(true,wordDictionarySolution1.search(".ad"));
25+
assertEquals(true,wordDictionarySolution1.search("b.."));
26+
}
27+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp