Friday, May 15, 2015

LeetCode [211] Add and Search Word - Data structure design

 211. Design Add and Search Words Data Structure

Medium

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

 

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

 

Constraints:

  • 1 <= word.length <= 500
  • word in addWord consists lower-case English letters.
  • word in search consist of  '.' or lower-case English letters.
  • At most 50000 calls will be made to addWord and search.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//C++: 46ms
class TrieNode {
public:
    bool isTail;
    char key;
    unordered_map<char, TrieNode*> children;

    // Initialize your data structure here.
    TrieNode():isTail(false){}
    TrieNode(char k):isTail(false),key(k){}
    
    bool findChild(char ch){
        return children.find(ch)!=children.end();
    }
    TrieNode * insertChildrend(char ch){
        TrieNode *newNode = new TrieNode(ch);
        children.insert(pair<char, TrieNode*>(ch, newNode));
        return newNode;
    }
    TrieNode * getChild(char ch){
        return children[ch];
    }
};


class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *p = root;
        for(auto ch:s){
            if(!p->findChild(ch)){
                TrieNode *newNode = p->insertChildrend(ch);
                p = newNode;
            }else{
                p = p->getChild(ch);
            }
        }
        if(p!=NULL){
            p->isTail = true;
        }
    }

    // Returns if the word is in the trie.
    bool search(string key, TrieNode *p, int index) {
        if(index>key.size()) return false;
        if(index==key.size()){
            if(p!=NULL && p->isTail) return true;
            else return false;
        }
        char ch = key[index];
        if(ch!='.'){
            if(p==NULL || !p->findChild(ch)){
                return false;
            }
            TrieNode *q = p->getChild(ch);
            return search(key, q, index+1);
        }else{
            for(auto it=p->children.begin(); it!=p->children.end(); ++it){
                TrieNode *q = it->second;
                if(search(key, q, index+1)) return true;
            }
            return false;
        }
    }    

    TrieNode* root;
};


class WordDictionary {
    Trie trie;
public:
    WordDictionary(){
        Trie trie=Trie();
    }

    // Adds a word into the data structure.
    void addWord(string word) {
       trie.insert(word);
    }

    // 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  trie.search(word, trie.root, 0);
    }
};

class TrieNode{
public:
    char key;
    bool isLeaf = false;
    TrieNode* children[26] = {NULL};
    TrieNode(){}
    TrieNode(char k):key(k){}
};

class Trie{
public:
    TrieNode *root = new TrieNode();
    Trie(){}
    void insert(string s){
        TrieNode *p = root;
        for(int i=0; i<(int)s.size(); ++i){
            char c = s[i];
            if(p->children[c-'a']==NULL){
                p->children[c-'a'] = new TrieNode(c);
            }
            p = p->children[c-'a'];
        }
        p->isLeaf = true;
    }

    bool search(string s){
        return search(s, s.size(), 0, root);
    }
    bool search(string s, int n, int i, TrieNode* p){
        if(i==n){
            return p->isLeaf;
        }else{
            char c = s[i];
            if(c!='.'){
                return p->children[c-'a']&&search(s, n, i+1, p->children[c-'a']);
            }else{
                for(char cc='a'; cc<='z'; ++cc){
                    if(p->children[cc-'a']&&search(s, n, i+1, p->children[cc-'a'])) return true;
                }
            }
            return false;
        }
    }
};

class WordDictionary {
    Trie trie;
public:

    // Adds a word into the data structure.
    void addWord(string word) {
        trie.insert(word);
    }

    // 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 trie.search(word);
    }
};
Posted by at
Labels: , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)