Design a data structure that supports the following two Operations:
void addWord(word) bool search(word) search(word) can search a literal word or a regular exPRession string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord(“bad”) addWord(“dad”) addWord(“mad”) search(“pad”) -> false search(“bad”) -> true search(“.ad”) -> true search(“b..”) -> true Note: You may assume that all words are consist of lowercase letters a-z.
class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isWord = false; TrieNode() {}}public class WordDictionary { TrieNode root; /** Initialize your data structure here. */ public WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ public void addWord(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 data structure. A word could contain the dot character '.' to represent any one letter. */ public boolean search(String word) { return backtrace(word, 0, root); } public boolean backtrace(String word, int start, TrieNode root) { if (start == word.length()) return root.isWord; if (word.charAt(start) != '.') { return root.children[word.charAt(start)-'a'] != null && backtrace(word, start+1, root.children[word.charAt(start)-'a']); } else { for (int i = 0; i < 26; i++) { if (root.children[i] != null) { if (backtrace(word, start+1, root.children[i])) return true; } } } return false; }}/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */class TrieNode {public: TrieNode* next[26]; bool isWord; TrieNode() { memset(next, 0, sizeof(next)); isWord = false; }};class WordDictionary {public: TrieNode* root; /** Initialize your data structure here. */ WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ void addWord(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 data structure. A word could contain the dot character '.' to represent any one letter. */ bool search(string word) { return backtrace(word, 0, root); } bool backtrace(string word, int index, TrieNode* node) { if (index == word.size()) return node->isWord; if (word[index] != '.') { return node->next[word[index]-'a'] != NULL && backtrace(word, index+1, node->next[word[index]-'a']); } else { for (int i = 0; i < 26; i++) { if (node->next[i] != NULL) { if (backtrace(word, index+1, node->next[i])) return true; } } } return false; }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */新闻热点
疑难解答
