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; } }