Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class WordDictionary {
- public:
- struct node
- {
- int val;
- node *v[26];
- node()
- {
- val = 0;
- for(int i=0; i<26; ++i)
- v[i]=NULL;
- }
- };
- node *root;
- /** Initialize your data structure here. */
- WordDictionary() {
- root = new node;
- }
- /** Adds a word into the data structure. */
- void addWord(string word) {
- add(root, word, 0);
- }
- void add(node *&root, string &word, int k)
- {
- if(k==word.length())
- root->val++;
- else
- {
- if(root->v[word[k]-'a']==NULL)
- root->v[word[k]-'a'] = new node;
- add(root->v[word[k]-'a'], word, k+1);
- }
- }
- /** 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 query(root, word, 0);
- }
- bool query(node *&root, string &word, int k)
- {
- if(k==word.length())
- return root->val;
- else
- {
- if(word[k]=='.')
- {
- bool ok=0;
- for(int i=0; i<26; ++i)
- if(root->v[i]!=NULL)
- ok|=query(root->v[i], word, k+1);
- return ok;
- }
- else
- {
- if(root->v[word[k]-'a']!=NULL)
- return query(root->v[word[k]-'a'], word, k+1);
- return 0;
- }
- }
- }
- };
- /**
- * Your WordDictionary object will be instantiated and called as such:
- * WordDictionary* obj = new WordDictionary();
- * obj->addWord(word);
- * bool param_2 = obj->search(word);
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement