0%

TrieTree

Implementation

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
Class TrieNode{
boolean isEnd;
TreeNode[] sons;
public TrieNode(){
sons = new TreeNode[26];
}
}

public void addWord(String s, TrieNode root){
TreeNode cur = root;
for (char ch: s.toCharArray()){
if (cur.sons[ch - 'a'] == null) cur.sons[ch - 'a'] = new TrieNode();
cur = cur.sons[ch -'a'];
}
cur.isEnd = true;
}

public boolean search(String s, TrieNode root){
TrieNode cur = root;
for (char ch: s.toCharArray()){
if (cur.sons[ch - 'a'] == null) return false;
cur = cur.sons[ch - 'a'];
}
if (cur.isEnd) return true;
return false;
}

public void main(){
TrieNode root = new TrieNode();
String word = "Congratulations";
addWord(word, root);
if (search(word, root)) System.out.println("Congratuations!");
}

#