# 逐步解析力扣208. 实现 Trie (前缀树/字典树)

``````class Trie {
Set<String> a = new HashSet<>();

public Trie() {

}

public void insert(String word) {
}

public boolean search(String word) {
return a.contains(word);
}

public boolean startsWith(String prefix) {
for (String s:a) {
if (s.startsWith(prefix)) return true;
}
return false;
}
}
``````

``````class Trie {
private Trie[] children;
private boolean isEnd;

public Trie() {
children = new Trie[26];
isEnd = false;
}

public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index]==null) node.children[index] = new Trie();
node = node.children[index];
}
node.isEnd = true;
}

public boolean search(String word) {
Trie node = searchPrefix(word);
return node !=null && node.isEnd;
}
private Trie searchPrefix(String prefix){
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index]==null) return null;
node = node.children[index];
}
return node;
}

public boolean startsWith(String prefix) {
return searchPrefix(prefix) !=null;
}
}
``````

`private Trie[] children;`

`private boolean isEnd;`

`int index = ch - 'a';`

`if (node.children[index]==null) node.children[index] = new Trie();`

node跳到子节点继续遍历
`node = node.children[index];`

THE END