C++ solution using backtracking


  • 1
    C
    class TrieNode {
    public:
        bool isWord;
        TrieNode *child[26];
        TrieNode(bool b = false) {
            for (int i = 0; i < 26; ++i) {
                child[i] = NULL;
            }
            isWord = b;
        }
    };
    class WordDictionary {
    public:
        WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode *node = root;
            for (auto i : word) {
                if (node->child[i - 'a'] == NULL) node->child[i - 'a'] = new TrieNode();
                node = node->child[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) {
            TrieNode *node = root;
            return search_helper(word, node, 0);
        }
        bool search_helper(string& word, TrieNode* node, int cur) {
            if (cur > word.size() || !node) return false;
            if (cur == word.size() && node->isWord) return true;
            for (int i = 0; i < 26; ++i) {
                if (word[cur] == '.' || (node->child[i] && i == word[cur]-'a')) {
                    bool ans = search_helper(word, node->child[i], cur + 1);
                    if (ans) return true;
                }
            }
            return false;
        }
        TrieNode *root;
    };

Log in to reply
 

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