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.
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
.
A:
思路很直接,就是 用 Trie 解决。 (这里,仍然需要自己定义TrieNode)
*********** Solution 1: Trie *******************
Mistakes:class WordDictionary { public: /** Initialize your data structure here. */ WordDictionary() { root = new TrieNode('2',true); } /** Adds a word into the data structure. */ void addWord(string word) { auto runner = root; for(int i =0;i<word.length();i++){ char ch = word[i]; if(runner->map.find(ch) == runner->map.end()){ TrieNode * tmp = new TrieNode(ch, i == word.length()-1); runner->map[ch] = tmp; } runner = runner->map[ch]; } runner->isEnd = 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 searchHelper(word, root); } private: struct TrieNode{ char ch; bool isEnd; unordered_map<char, TrieNode*> map; TrieNode(char curChar, bool end){ ch = curChar; isEnd = end; } }; bool searchHelper(string word, const TrieNode* node){ if(word.length() ==0) return node->isEnd; auto runner = root; char ch = word[0]; if(ch == '.'){ auto iter = node->map.begin(); while(iter != node->map.end()){ int subResult = searchHelper(word.substr(1), iter->second ); if(subResult) return true; iter++; } } if(node->map.find(ch) == node->map.end()){ return false; }else{ return searchHelper(word.substr(1), node->map.find(ch)->second); } } TrieNode *root; }; /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary* obj = new WordDictionary(); * obj->addWord(word); * bool param_2 = obj->search(word); */
第二次 Trie Node 用的array,而非HashMap
public class WordDictionary { TrieNode root = new TrieNode(); // Adds a word into the data structure. public void addWord(String word) { aHelper(word,root); } private void aHelper(String word, TrieNode root){ if(word.length()==0){ root.isLeaf = true; return; } char ch = word.charAt(0); if(root.child[ch-'a'] ==null) root.child[ch-'a'] = new TrieNode(); aHelper(word.substring(1),root.child[ch-'a']); } // 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 sHelper(root,word); } private boolean sHelper(TrieNode root, String word){ if(root == null) return false; if(word.length()==0) return root.isLeaf; char ch = word.charAt(0); word = word.substring(1); if(ch != '.'){ return sHelper(root.child[ch-'a'], word); }else{ for(int i =0;i< 26;i++){ if( sHelper(root.child[i], word)) return true; } return false; } } } class TrieNode{ public boolean isLeaf; TrieNode child[] ; public TrieNode(){ child = new TrieNode[26]; isLeaf = false; } } // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary = new WordDictionary(); // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
No comments:
Post a Comment