Ternary Search Trie(TST) with C++


  • 0
    M

    although the time complexity is O(lg(n)), it would save some space

    class TrieNode {
        public:
    // Initialize your data structure here.
    
    bool is_end;
    
    /* T-ST implemention */
    TrieNode *left, *mid, *right;
    char c;
    
    TrieNode(char _c):c(_c),left(NULL),mid(NULL),right(NULL),is_end(false){
        
    }
    ~TrieNode(){
        if(left)
            delete left;
        if(right)
            delete right;
        if(mid)
            delete mid;
     }
    };
    
    class Trie {
        public:
        Trie() {
            root = NULL;
        }
        ~Trie(){
            delete root;
        }
    
    TrieNode *put(TrieNode *node, const string &str, int index){
        if(!node){
            node = new TrieNode(str[index]);
        }
        
        if(node->c > str[index])
            node->left = put(node->left, str, index);
        else if(node->c < str[index])
            node->right = put(node->right, str, index);
        else if(index < str.size()-1){
            node->mid = put(node->mid, str, index+1);
        }else
            node->is_end = true;
        
        return node;
    }
    // Inserts a word into the trie.
    void insert(string word) {
        root = put(root, word, 0);
    }
    
    // Returns if the word is in the trie.
    TrieNode *get(TrieNode *node, const string &str, int index){
        if(node == NULL)
            return NULL;
            
        if(node->c > str[index])
            return get(node->left, str, index);
        if(node->c < str[index])
            return get(node->right, str, index);
        if(index < str.size()-1)
            return get(node->mid, str, index+1);
        return node;
    }
    bool search(string word) {
        TrieNode *p = get(root, word, 0);
    
        return p&&p->is_end;
    }
    
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *p = get(root, prefix, 0);
    
        return p!=NULL;
    }
    
    private:
        TrieNode* root;
    };

  • 0
    G

    @mzeric should pass node by reference in put method...right?


  • 0
    G

    @gdou2 sorry passing by value is certainly OK that way


Log in to reply
 

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