Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowercase letters a-z.
class TrieNode { boolean isWord = false; TrieNode[] children = new TrieNode[26]; public TrieNode () {}}public class Trie { TrieNode root; /** Initialize your data structure here. */ public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String word) { TrieNode tn = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (tn.children[c - 'a'] == null) { tn.children[c - 'a'] = new TrieNode(); } tn = tn.children[c - 'a']; } tn.isWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { TrieNode tn = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (tn.children[c - 'a'] == null) return false; tn = tn.children[c - 'a']; } return tn.isWord; } /** Returns if there is any word in the trie that starts with the given PRefix. */ public boolean startsWith(String prefix) { TrieNode tn = root; for (int i = 0; i < prefix.length(); i++) { char c = prefix.charAt(i); if (tn.children[c - 'a'] == null) return false; tn = tn.children[c - 'a']; } return true; }}/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */class TrieNode {public: TrieNode* next[26]; bool isWord; TrieNode() { memset(next, 0, sizeof(next)); isWord = false; }};class Trie {public: /** Initialize your data structure here. */ TrieNode* root; Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ void insert(string word) { TrieNode* tn = root; for (int i = 0; i < word.size(); i++) { char c = word[i]; if (tn->next[c-'a'] == NULL) { tn->next[c-'a'] = new TrieNode(); } tn = tn->next[c-'a']; } tn->isWord = true; } /** Returns if the word is in the trie. */ bool search(string word) { TrieNode* tn = root; for (int i = 0; i < word.size(); i++) { char c = word[i]; if (tn->next[c-'a'] == NULL) return false; tn = tn->next[c-'a']; } return tn->isWord; } /** Returns if there is any word in the trie that starts with the given prefix. */ bool startsWith(string prefix) { TrieNode* tn = root; for (int i = 0; i < prefix.size(); i++) { char c = prefix[i]; if (tn->next[c-'a'] == NULL) return false; tn = tn->next[c-'a']; } return true; }};/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * bool param_2 = obj.search(word); * bool param_3 = obj.startsWith(prefix); */新闻热点
疑难解答
