C – recursive solution, 44 ms


  • 0
    S
    struct TrieNode {
        bool included;
        struct TrieNode* children[26];
    };
    
    /** Initialize your data structure here. */
    struct TrieNode* trieCreate() {
        struct TrieNode *newTreeNode = malloc(sizeof(struct TrieNode));
        
        newTreeNode->included = false;
        for(int i = 0 ; i < 26 ; i++) newTreeNode->children[i] = NULL;
        
        return newTreeNode;
    }
    
    /** Inserts a word into the trie. */
    void insert(struct TrieNode* root, char* word) {
        
        int wordLenght = strlen(word);
        if (wordLenght > 0) {
            
            // create subtree of necessary
            if(root->children[word[0]-'a'] == NULL) root->children[word[0]-'a'] = trieCreate();
            
            if(wordLenght == 1) {
                // set 'included' flag
                root->children[word[0]-'a']->included = true;
            } else {
                // insert the other characters
                insert(root->children[word[0]-'a'], word + 1);
            }
            
        }
    }
    
    /** Returns if the word is in the trie. */
    bool search(struct TrieNode* root, char* word) {
        
        int wordLenght = strlen(word);
        if(wordLenght == 0) return false;
        
        struct TrieNode* child = root->children[word[0]-'a'];
        
        if(child == NULL) return false; // cant continue this way
        if(wordLenght == 1) return child->included; // this was the last character – lets return whether it's included
        return search(child, word + 1); // search deeper
        
    }
    
    /** Returns if there is any word in the trie 
        that starts with the given prefix. */
    bool startsWith(struct TrieNode* root, char* prefix) {
        
        int prefixLenght = strlen(prefix);
        if(prefixLenght == 0) return true;
        
        struct TrieNode* child = root->children[prefix[0]-'a'];
        
        if(child == NULL) return false;
        if(prefixLenght == 1) return true;
        
        return startsWith(child, prefix + 1);
    }
    
    /** Deallocates memory previously allocated for the TrieNode. */
    void trieFree(struct TrieNode* root) {
        
        if(root != NULL) {
        
            for(int i = 0 ; i < 26 ; i++) trieFree(root->children[i]);
            free(root);
        }
        
    }

Log in to reply
 

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