标签:char word Trie 208 public tn TrieNode Implement children
Implement a trie with insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z
.
class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children;
public TrieNode(char c) {
this.val = c;
this.isWord = false;
this.children = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode(' ');
}
public void insert(String word) {
TrieNode tn = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (tn.children[c - 'a'] == null)
tn.children[c - 'a'] = new TrieNode(c);
tn = tn.children[c - 'a'];
}
tn.isWord = true;
}
public boolean search(String word) {
TrieNode tn = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (tn.children[c - 'a'] == null)
return false;
tn = tn.children[c - 'a'];
}
return tn.isWord;
}
public boolean startsWith(String prefix) {
TrieNode tn = root;
for(int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (tn.children[c - 'a'] == null)
return false;
tn = tn.children[c - 'a'];
}
return true;
}
}
标签:char,
word,
Trie,
208,
public,
tn,
TrieNode,
Implement,
children
From: https://www.cnblogs.com/MarkLeeBYR/p/16921172.html