力扣-208.实现Trie(前缀树)

题目链接

208.实现Trie(前缀树)

class Trie {Trie[] children;boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;int len = word.length();for (int i = 0; i < len; i++) {int index = word.charAt(i) - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];if (i == len - 1) {node.isEnd = true;}}}public boolean search(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {int index = word.charAt(i) - 'a';if (node.children[index] == null)return false;node = node.children[index];}return node.isEnd;}public boolean startsWith(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {int index = prefix.charAt(i) - 'a';if (node.children[index] == null)return false;node = node.children[index];}return true;}
}

小结：前缀树是一个类似26叉树，并有一个额外标记是否为字符串结尾，插入的时候用一个结点指针依次扫描字符串每一位，不存在则新建。