40ms C array as map solution


  • 0
    C
    struct TrieNode {
        char c;
        struct TrieNode* children[26];
        bool isLeaf;
    };
    
    /** Initialize your data structure here. */
    struct TrieNode* trieCreate() 
    {
        struct TrieNode* nd = (struct TrieNode*)malloc(sizeof(struct TrieNode));
        nd->c = '\0';
        nd->isLeaf = false;
        memset(nd->children, 0, sizeof(struct TrieNode*)*26);
        
        return nd;
    }
    
    /** Inserts a word into the trie. */
    void insert(struct TrieNode* root, char* word) 
    {
        struct TrieNode* nd = NULL;
        struct TrieNode** children = root->children;
        char* ch = word;
        
        while (*ch != '\0')
        {
            struct TrieNode* t = children[*ch-'a'];
            if (t == NULL)
            {
                nd = trieCreate();
                nd->c = *ch;
                children[*ch-'a'] = nd;
            }
            else
            {
                nd = t ;
            }
            
            children = nd->children;
            ch++;
    
            if (*ch == '\0')
            {
                nd->isLeaf = true;
            }
        }
        
    }
    
    /** Returns if the word is in the trie. */
    bool search(struct TrieNode* root, char* word) {
        
       struct TrieNode* nd = NULL;
       struct TrieNode** children = root->children;
       char* ch = word;
    
       while (*ch != '\0')
       {
          struct TrieNode* t = children[*ch-'a'];
          if (t == NULL)
          {
             return false;
          }
          else
          {
             nd = t ;
          }
    
          children = nd->children;
          ch++;
       }
       
       if (nd->isLeaf != true)
          return false;
    
       return true;
    }
    
    /** Returns if there is any word in the trie 
        that starts with the given prefix. */
    bool startsWith(struct TrieNode* root, char* prefix) {
    
       struct TrieNode* nd = NULL;
       struct TrieNode** children = root->children;
       char* ch = prefix;
    
       while (*ch != '\0')
       {
          struct TrieNode* t = children[*ch-'a'];
          if (t == NULL)
          {
             return false;
          }
          else
          {
             nd = t ;
          }
    
          children = nd->children;
          ch++;
       }
    
       return true;
    }
    
    void trieFreeChildren(struct TrieNode* node)
    {
       int i;
    
       if (node->isLeaf == false)
       {
          for (i=0;i<26;i++)
          {
             if (node->children[i] != NULL)
                trieFreeChildren(node->children[i]);
          }
       }
    
       if (node != NULL)
       {
          free(node);
       }
    
    }
    
    /** Deallocates memory previously allocated for the TrieNode. */
    void trieFree(struct TrieNode* root) {
        trieFreeChildren(root);
    }
    
    // Your Trie object will be instantiated and called as such:
    // struct TrieNode* node = trieCreate();
    // insert(node, "somestring");
    // search(node, "key");
    // trieFree(node);

Log in to reply
 

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