208. 实现 Trie (前缀树)
题解
执行用时:42 ms, 在所有 Java 提交中击败了60.29%的用户 内存消耗:47.1 MB, 在所有 Java 提交中击败了91.73%的用户
class Trie {
private Node root;
private static class Node {
// 当前字符
char c;
// 当前字符是否可构成一个单词
boolean isWord;
// 树的分支
Node[] childedList;
public Node(char c) {
this.c = c;
this.isWord = false;
this.childedList = new Node[26];
}
}
/** Initialize your data structure here. */
public Trie() {
// 树根初使化为一个空字符
this.root = new Node(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
int length = word.length();
Node cur = root;
for (int i = 0; i < length; i++) {
char curChar = word.charAt(i);
if (cur.childedList[curChar - 'a'] == null) {
cur.childedList[curChar - 'a'] = new Node(curChar);
}
cur = cur.childedList[curChar - 'a'];
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node node = searchReturnNode(word);
if (node == null) {
return false;
}
return node.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Node node = searchReturnNode(prefix);
return node != null;
}
// 返回一个节点,可以给 search 和 startsWith 方法复用
private Node searchReturnNode(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char curChar = word.charAt(i);
if (cur.childedList[curChar - 'a'] != null) {
cur = cur.childedList[curChar - 'a'];
} else {
return null;
}
}
return cur;
}
}