Short C++ Trie solution (using C++11 smart pointers)


  • 0
    class WordDictionary {
        Trie dic;
    public:
        void addWord(string w) { dic.add(w); }
        bool search(string w) { return dic.search(w); }
    };
    
    class Trie {
        struct TrieNode {
            unique_ptr<TrieNode> children[26];
            bool word_end = false;
        };
        unique_ptr<TrieNode> root;
        bool partialSearch(TrieNode* node, const string &w, int i) {
            if (!node) return false;
            if (i >= w.size()) return node->word_end;
            if (w[i] != '.') return partialSearch(node->children[w[i] - 'a'].get(), w, i+1);
            for (int j = 0; j < 26; j++)
                if (node->children[j] && partialSearch(node->children[j].get(), w, i+1))
                    return true;
            return false;
        }
    public:
        Trie() : root(new TrieNode()) {}
        bool search(const string &w) { return partialSearch(root.get(), w, 0); }
        void add(const string &w) {
            auto node = root.get();
            for (char ch : w) {
                if (!node->children[ch - 'a'])
                    node->children[ch - 'a'].reset(new TrieNode());
                node = node->children[ch - 'a'].get();
            }
            node->word_end = true;
        }
    };
    

Log in to reply
 

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