Leetcode 208 Solution

This article provides solution to leetcode question 208 (implement-trie-prefix-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 208" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/implement-trie-prefix-tree

Solution

class TrieNode {
public:
    TrieNode* m_children[26] = {0};
    bool m_leaf = false;
};



class Trie {
public:
    Trie() {
        root = new TrieNode();
    }



    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* nextnode = root;



        for (int i = 0; i < word.size(); i++)
        {
            char ch = word[i];
            if (nextnode->m_children[ch - 'a'] == NULL)
                nextnode->m_children[ch - 'a'] = new TrieNode();
            nextnode = nextnode->m_children[ch - 'a'];
        }



        nextnode->m_leaf = true;
    }



    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* nextnode = root;



        for (int i = 0; i < word.size(); i++)
        {
            char ch = word[i];
            if (nextnode->m_children[ch - 'a'] == NULL)
                return false;
            nextnode = nextnode->m_children[ch - 'a'];
        }



        return nextnode->m_leaf;
    }



    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* nextnode = root;



        for (int i = 0; i < prefix.size(); i++)
        {
            char ch = prefix[i];
            if (nextnode->m_children[ch - 'a'] == NULL)
                return false;
            nextnode = nextnode->m_children[ch - 'a'];
        }



        return true;
    }



private:
    TrieNode* root;
};



// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");