Trie plus DFS solution


  • 0
    class WordDictionary {
    public:
    
        bool isWord = false;
        vector<WordDictionary*> next = vector<WordDictionary*>(26, NULL);
    
        WordDictionary() {}
    
        /** Adds a word into the data structure. */
        void addWord(string word) {
            WordDictionary *p = this;
            for (char c : word) {
                if (!p->next[c -= 'a']) 
                    p->next[c] = new WordDictionary();
                p = p->next[c];
            }
            p->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) {
            WordDictionary *p = this;
            stack<pair<WordDictionary*, int> > s;
            s.push(make_pair(p, 0));
            while (s.size()) {
                p = s.top().first;
                int idx = s.top().second;
                s.pop();
                if (idx == word.size()) {
                    if (p->isWord) return true;
                    continue;
                }
                if (word[idx] == '.') {
                    for (WordDictionary* wd : p->next) {
                        if (wd) s.push(make_pair(wd, idx + 1));
                    }
                } else {
                    if (p->next[word[idx] - 'a']) 
                        s.push(make_pair(p->next[word[idx] - 'a'], idx + 1));
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.