题目大意：
实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true说明:
- 你可以假设所有的输入都是由小写字母
a-z构成的。 - 保证所有输入均为非空字符串。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=208
解题思路分析：
Trie被称为前缀树，也叫做字典树，它是一个经典的树形结构。既然是树形结构，那么就少不了节点，对于字典树的节点我们可以定义为：
class Node{
// 是否存在以当前节点结尾的单词
boolean isWord;
// 当前节点的后续字符
Node[] children = new Node[26];
}我们在之前的文章中非常详细的介绍过有关字典树Trie的的数据存储结构：LEETCODE 1268. Search Suggestions System 解题思路分析，这里就不再重复了。本题可以说是字典树最为简单的一个应用场景，如果你是第一次接触到这个概念或者你对字典树还不够了解，强烈建议你先去学习一下上面这篇文章。
实现代码：
class Node{
boolean isWord;
Node[] children = new Node[26];
}
Node root = new Node();
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node node = root;
char[] arr = word.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) children[c-'a'] = new Node();
node=children[c-'a'];
}
node.isWord=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node node = root;
char[] arr = word.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) return false;
node=children[c-'a'];
}
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 = root;
char[] arr = prefix.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) return false;
node=children[c-'a'];
}
return true;
}本题解法执行时间为29ms。
Runtime: 29 ms, faster than 98.16% of Java online submissions for Implement Trie (Prefix Tree).
Memory Usage: 50.3 MB, less than 100.00% of Java online submissions for Implement Trie (Prefix Tree).
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-208-implement-trie-prefix-tree-解题思路分析/