17
05/2015
[LeetCode] Add and Search Word - Data structure design
Add and Search Word - Data structure design
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
.
解题思路:
运用前缀树来实现词典的查询。唯一不同的是有通配符.,对于通配符,运用暴力回溯搜索法即可。
struct dictionaryNode{ public: dictionaryNode* sons[26]; bool isWord; dictionaryNode(){ for(int i=0; i<26; i++){ sons[i]=NULL; } isWord=false; } ~dictionaryNode(){ for(int i=0; i<26; i++){ if(sons[i]!=NULL){ delete sons[i]; sons[i]=NULL; } } } }; class WordDictionary { public: dictionaryNode* root; WordDictionary(){ root=new dictionaryNode(); } ~WordDictionary(){ if(root!=NULL){ delete root; root = NULL; } } // Adds a word into the data structure. void addWord(string word) { dictionaryNode* node = root; int len=word.length(); for(int i=0; i<len; i++){ if(node->sons[word[i]-'a']==NULL){ node->sons[word[i]-'a'] = new dictionaryNode(); } node = node->sons[word[i]-'a']; } node->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 searchHelp(root, word, 0); } bool searchHelp(dictionaryNode* node, string& word, int i){ if(node==NULL){ return false; } int len = word.length(); if(i>=len){ return node->isWord; } if(word[i]!='.'){ return searchHelp(node->sons[word[i]-'a'], word, i+1); }else{ for(int k=0; k<26; k++){ if(searchHelp(node->sons[k], word, i+1)){ return true; } } return false; } } }; // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary; // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
0 条评论