C++ using Trie and DFS for search. easy understand solution


  • 11
    L
     struct Trie {
         vector<Trie *> child;
         bool isWord;
         Trie() : isWord(false), child(vector<Trie *>(26, nullptr)) {}
     };
     Trie *root;
     WordDictionary() : root(new Trie()) {}
    
    void addWord(string word) {
        const int size_w = word.size();
        Trie *cur = root;
        for (int i = 0; i < size_w; i++) {
            int index = word[i] - 'a';
            if (!cur->child[index]) cur->child[index] = new Trie();
            cur = cur->child[index];
        }
        cur->isWord = true;
    }
    
    bool search(string word) {
        return search(word.c_str(), root);
    }
    bool search(const char *ch, TrieNode *cur) {
        if (!cur) return false;
        if (*ch == '\0') return cur->isWord;
        if (*ch != '.') {
             return search(ch+1, cur->child[*ch - 'a']);
        } else {
            for (int i = 0; i <= 25; i++) {
                if (search(ch+1, cur->child[i])) return true;
            }
            return false;
        }
    }

  • 0
    N

    Your DFS is clearly, however, when *key = '.' and all search(key+1, cur->child[i]) return false, search(const char *key, Trie *cur) will return nothing.


  • 0
    L

    Thank you for remind. It should return false after trying 26 childrens.
    I have changed the code according your suggestion.


  • 1

    There are some typing errors in your pasted code -> the type of the second parameter in the second function search should be <font color="#ff0000">Trie</font> instead of <font color="#00ff00">TrieNode</font>

    Rearranged them and there is the valid one, anyway, thanks for your sharing. But I think it will be a better choice to past all the code which can be easily tested. So many thanks for sharing!

    struct Trie 
    {
         vector<Trie *> child;
         bool isWord;
         Trie() : isWord(false), child(vector<Trie *>(26, nullptr)) {}
     };
    
    class WordDictionary {
    public:
     Trie *root;
     WordDictionary() : root(new Trie()) {}
    
    void addWord(string word) {
        const int size_w = word.size();
        Trie *cur = root;
        for (int i = 0; i < size_w; i++) {
            int index = word[i] - 'a';
            if (!cur->child[index]) cur->child[index] = new Trie();
            cur = cur->child[index];
        }
        cur->isWord = true;
    }
    
    bool search(string word) {
        return search(word.c_str(), root);
    }
    bool search(const char *ch, Trie *cur) {
        if (!cur) return false;
        if (*ch == '\0') return cur->isWord;
        if (*ch != '.') {
             return search(ch+1, cur->child[*ch - 'a']);
        } else {
            for (int i = 0; i <= 25; i++) {
                if (search(ch+1, cur->child[i])) return true;
            }
            return false;
        }
    }
    };
    

  • 0

    There is a <font color="#0000ff">C version</font> of your code with some improvements:

    again thanks for your sharing!


Log in to reply
 

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