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

Commit3d90a93

Browse files
solves trie #208 in java
1 parent6e51450 commit3d90a93

File tree

3 files changed

+67
-2
lines changed

3 files changed

+67
-2
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -168,7 +168,7 @@
168168
| 205|[Isomorphic Strings](https://leetcode.com/problems/isomorphic-strings)|[![Java](assets/java.png)](src/IsomorphicStrings.java)[![Python](assets/python.png)](python/isomorphic_strings.py)||
169169
| 206|[Reverse Linked List](https://leetcode.com/problems/reverse-linked-list)|[![Java](assets/java.png)](src/ReverseLinkedList.java)[![Python](assets/python.png)](python/reverse_linked_list.py)||
170170
| 207|[Course Schedule](https://leetcode.com/problems/course-schedule)|[![Java](assets/java.png)](src/CourseSchedule.java)||
171-
| 208|[Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree)|||
171+
| 208|[Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree)|[![Java](assets/java.png)](src/Trie.java)||
172172
| 209|[Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum)|||
173173
| 210|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii)|||
174174
| 211|[Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure)|||

‎src/HelloWorld.java

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
11
publicclassHelloWorld {
22
publicstaticvoidmain(String[]args) {
3-
System.out.println("Hello world");
3+
Trietrie =newTrie();
4+
trie.insert("apple");
5+
// System.out.println(trie.search("apple"));
6+
// System.out.println(trie.search("app"));
7+
System.out.println(trie.startsWith("app"));// true
8+
trie.insert("app");
9+
// System.out.println(trie.search("app"));
410
}
511
}

‎src/Trie.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// https://leetcode.com/problems/implement-trie-prefix-tree
2+
// insertion
3+
// T: O(n)
4+
// S: O(n)
5+
// search
6+
// T: O(n)
7+
// S: O(n)
8+
// starts with
9+
// T: O(n)
10+
// S: O(n)
11+
12+
publicclassTrie {
13+
privatefinalTrie[]alphabet =newTrie[26];
14+
privatebooleanisWordEnd =false;
15+
16+
publicTrie() { }
17+
18+
publicvoidinsert(Stringword) {
19+
insert(word,0);
20+
}
21+
22+
privatevoidinsert(Stringword,intindex) {
23+
if (index ==word.length()) {
24+
this.isWordEnd =true;
25+
return;
26+
}
27+
intcharIndex =toIndex(word.charAt(index));
28+
if (alphabet[charIndex] ==null) {
29+
alphabet[charIndex] =newTrie();
30+
}
31+
alphabet[charIndex].insert(word,index +1);
32+
}
33+
34+
publicbooleansearch(Stringword) {
35+
returnsearch(word,0);
36+
}
37+
38+
publicbooleansearch(Stringword,intindex) {
39+
if (index ==word.length())returnisWordEnd;
40+
intcharIndex =toIndex(word.charAt(index));
41+
if (alphabet[charIndex] ==null)returnfalse;
42+
returnalphabet[charIndex].search(word,index +1);
43+
}
44+
45+
publicbooleanstartsWith(Stringprefix) {
46+
returnstartsWith(prefix,0);
47+
}
48+
49+
publicbooleanstartsWith(Stringprefix,intindex) {
50+
if (index ==prefix.length())returntrue;
51+
intcharIndex =toIndex(prefix.charAt(index));
52+
if (alphabet[charIndex] ==null)returnfalse;
53+
returnalphabet[charIndex].startsWith(prefix,index +1);
54+
}
55+
56+
privateinttoIndex(charc) {
57+
returnc -'a';
58+
}
59+
}

0 commit comments

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