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

Commitfe26497

Browse files
committed
implement_trie_208: solved
1 parent3c02040 commitfe26497

File tree

3 files changed

+163
-0
lines changed

3 files changed

+163
-0
lines changed

‎implement_trie_208/README.md‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#208. Implement Trie (Prefix Tree)
2+
3+
https://leetcode.com/problems/implement-trie-prefix-tree/
4+
5+
##Difficulty:
6+
7+
Medium
8+
9+
##Description
10+
11+
Implement a trie with insert, search, and startsWith methods.
12+
13+
Example:
14+
```
15+
Trie trie = new Trie();
16+
17+
trie.insert("apple");
18+
trie.search("apple"); // returns true
19+
trie.search("app"); // returns false
20+
trie.startsWith("app"); // returns true
21+
trie.insert("app");
22+
trie.search("app"); // returns true
23+
```
24+
25+
Note:
26+
- You may assume that all inputs are consist of lowercase letters a-z.
27+
- All inputs are guaranteed to be non-empty strings.

‎implement_trie_208/solution.go‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package implement_trie_208
2+
3+
typeTriestruct {
4+
root*trieNode
5+
}
6+
7+
typetrieNodestruct {
8+
charbyte
9+
endbool
10+
children [26]*trieNode
11+
}
12+
13+
// Returns a Trie
14+
funcConstructor()Trie {
15+
returnTrie{
16+
root:&trieNode{},
17+
}
18+
}
19+
20+
// Inserts a word into the trie
21+
func (this*Trie)Insert(wordstring) {
22+
curr:=this.root
23+
fori:=0;i<len(word);i++ {
24+
slot:=word[i]-'a'
25+
26+
// If the child doesn't exist, create it
27+
ifcurr.children[slot]==nil {
28+
curr.children[slot]=&trieNode{
29+
char:word[i],
30+
}
31+
}
32+
33+
// Advance curr to the slot
34+
curr=curr.children[slot]
35+
}
36+
37+
// Mark the last node as the end of an inserted word
38+
curr.end=true
39+
}
40+
41+
// Returns true if the word is in the trie
42+
func (this*Trie)Search(wordstring)bool {
43+
returnthis.search(word,true)
44+
}
45+
46+
// Returns true if there is any word in the trie that starts with the given prefix
47+
func (this*Trie)StartsWith(prefixstring)bool {
48+
returnthis.search(prefix,false)
49+
}
50+
51+
func (this*Trie)search(wordstring,needsEndbool)bool {
52+
curr:=this.root
53+
fori:=0;i<len(word);i++ {
54+
slot:=word[i]-'a'
55+
ifcurr.children[slot]==nil {
56+
returnfalse
57+
}
58+
59+
curr=curr.children[slot]
60+
}
61+
62+
ifneedsEnd {
63+
returncurr.end
64+
}
65+
66+
returntrue
67+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package implement_trie_208
2+
3+
import (
4+
"github.com/stretchr/testify/assert"
5+
"testing"
6+
)
7+
8+
funcTestTrie(t*testing.T) {
9+
typeoperationstruct {
10+
methodstring
11+
valuestring
12+
wantbool
13+
}
14+
15+
testCases:= []struct {
16+
namestring
17+
ops []operation
18+
}{
19+
{
20+
name:"trie test",
21+
ops: []operation{
22+
{
23+
method:"Insert",
24+
value:"apple",
25+
},
26+
{
27+
method:"Search",
28+
value:"apple",
29+
want:true,
30+
},
31+
{
32+
method:"Search",
33+
value:"app",
34+
want:false,
35+
},
36+
{
37+
method:"StartsWith",
38+
value:"app",
39+
want:true,
40+
},
41+
{
42+
method:"Insert",
43+
value:"app",
44+
},
45+
{
46+
method:"Search",
47+
value:"app",
48+
want:true,
49+
},
50+
},
51+
},
52+
}
53+
54+
for_,tt:=rangetestCases {
55+
t.Run(tt.name,func(t*testing.T) {
56+
trie:=Constructor()
57+
for_,op:=rangett.ops {
58+
switchop.method {
59+
case"Insert":
60+
trie.Insert(op.value)
61+
case"Search":
62+
assert.Equal(t,op.want,trie.Search(op.value))
63+
case"StartsWith":
64+
assert.Equal(t,op.want,trie.StartsWith(op.value))
65+
}
66+
}
67+
})
68+
}
69+
}

0 commit comments

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