C++ clean code using trie


  • 0
    L
    public:
    class trieNode {
        friend class WordDictionary;
        bool isWord;
        vector<trieNode *> children;
        trieNode() : isWord(false), children(vector<trieNode *>(26, nullptr)){}
    };
    trieNode *root;
    WordDictionary() : root(new trieNode()) {}
    // Adds a word into the data structure.
    void addWord(string word) {
        trieNode *cur = root;
        const int size_w = word.size();
        for (int i = 0; i < size_w; i++) {
            int index = word[i] - 'a';
            if (!cur->children[index]) {
                cur->children[index] = new trieNode();
            }
            cur = cur->children[index];
        }
        cur->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) {
        return search(word.c_str(), root);
    }
    bool search(const char *key, trieNode *cur) {
        if (!cur) return false;
        if (*key == '\0') return cur->isWord;
        if (*key == '.') {
            for (int i = 0; i < 26; i++) {
                if (cur->children[i]) {
                    if (search(key+1, cur->children[i])) return true;
                }
            }
        } else {
            int index = *key - 'a';
            if (!cur->children[index]) return false;
            return search(key + 1, cur->children[index]);
        }
    }

Log in to reply
 

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