LintCode 442. Implement Trie 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/implement-trie/
Implement a trie with insert, search, and startsWith methods.
Example
insert("lintcode")
search("code")
>>> false
startsWith("lint")
>>> true
startsWith("linterror")
>>> false
insert("linterror")
search("lintcode)
>>> true
startsWith("linterror")
>>> true
解题思路
题目是考察Trie字典树的实现。
理解字典树的结构，就会很容易用代码实现字典树。字典树每个结点TrieNode都有个长度大小为26的TrieNode数组和表示是否是单词的boolean变量hasWord。Trie的基本操作包括insert、search、startWith。
参考代码
/**
* Your Trie object will be instantiated and called as such:
* Trie trie = new Trie();
* trie.insert("lintcode");
* trie.search("lint"); will return false
* trie.startsWith("lint"); will return true
*/
class TrieNode {
public TrieNode[] children;
public boolean hasWord;
// Initialize your data structure here.
public TrieNode() {
this.children = new TrieNode[26];
this.hasWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (p.children[c] == null) {
p.children[c] = new TrieNode();
}
p = p.children[c];
}
p.hasWord = true;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode p = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (p.children[c] == null) {
return false;
}
p = p.children[c];
}
return p.hasWord;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = root;
for (int i = 0; i < prefix.length(); i++) {
int c = prefix.charAt(i) - 'a';
if (p.children[c] == null) {
return false;
}
p = p.children[c];
}
return true;
}
}