[Implement Trie (Prefix Tree)] [C++] - Clean Code (array | map)


  • 4

    array

    class Trie {
    public:
        Trie() {}
    
        void insert(string word) {
            Trie* node = this;
            for (char ch : word) {
                ch -= 'a';
                if (!node->next[ch]) { node->next[ch] = new Trie(); }
                node = node->next[ch];
            }
            node->isword = true;
        }
    
        bool search(string word) {
            Trie* node = this;
            for (char ch : word) {
                ch -= 'a';
                if (!node->next[ch]) { return false; }
                node = node->next[ch];
            }
            return node->isword;
        }
    
        bool startsWith(string prefix) {
            Trie* node = this;
            for (char ch : prefix) {
                ch -= 'a';
                if (!node->next[ch]) { return false; }
                node = node->next[ch];
            }
            return true;
        }
    
    private:
        Trie* next[26] = {};
        bool isword = false;
    };
    

    map

    class Trie {
    public:
        Trie() {}
    
        void insert(string word) {
            Trie* node = this;
            for (char ch : word) {
                if (!node->next.count(ch)) { node->next[ch] = new Trie(); }
                node = node->next[ch];
            }
            node->isword = true;
        }
    
        bool search(string word) {
            Trie* node = this;
            for (char ch : word) {
                if (!node->next.count(ch)) { return false; }
                node = node->next[ch];
            }
            return node->isword;
        }
    
        bool startsWith(string prefix) {
            Trie* node = this;
            for (char ch : prefix) {
                if (!node->next.count(ch)) { return false; }
                node = node->next[ch];
            }
            return true;
        }
    
    private:
        map<char, Trie*> next = {};
        bool isword = false;
    };
    

  • 0

    Can I ask you that what's the difference between these two solutions?


  • 0

    @Hao-Cai using array[26] as internal storage can only handle [a-z]. using map you can store any character from 0~255 as the next nodes.


  • 0

    Yes, you are right! Thank you!


Log in to reply
 

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