algorithm - Implement a trie with insert, search, and startsWith methods in C from LeetCode. -
implement trie insert, search, , startswith methods.
note: may assume inputs consist of lowercase letters a-z.
i have written simple solution implementing trie in c, has passed 16 test cases leetcode.
any recommendation or suggestion ?
//node structure struct trienode { char value; int count; struct trienode * children[27]; }; static int count =0; /** initialize data structure here. */ //return root pointer struct trienode* triecreate() { struct trienode *pnode = null; pnode = (struct trienode *)malloc(sizeof(struct trienode)); if (pnode) { pnode->value = '\0'; pnode->count =0; memset(pnode->children, 0, sizeof(pnode->children)); } return pnode; } /** inserts word trie. */ void insert(struct trienode* root, char* word) { struct trienode *pcrawl = root; count ++; //check if word not empty if(word){ int index=0, =0; //check if root not empty if (root){ while( word[i] != '\0'){ index = ( (int) (word[i]) - (int)'a'); if(!pcrawl->children[index]) { pcrawl->children[index] = triecreate(); pcrawl->children[index]->value = word[i]; } pcrawl = pcrawl->children[index]; i++; } //count !=0 tell last node;; pcrawl->count = count; } }} /** returns if word in trie. */ bool search(struct trienode * root, char* word) { struct trienode *pcrawl = root; bool flag = false; //check if word null if(!word) return false; //if trie empty if(!root) { return false; } //if word empty if (*word == '\0') { return true; } int i=0, index =0 ; while (word[i] != '\0') { index = ((int) (word[i]) - (int)'a'); //// if node/character not in trie if(!pcrawl->children[index]) { flag = false; break; } pcrawl = pcrawl->children[index]; i++; } //count != 0 marks node last / leaf node if(pcrawl->count != 0 && word[i] == '\0') { flag = true; } return flag; } /** returns if there word in trie starts given prefix. */ bool startswith(struct trienode* root, char* prefix) { struct trienode * pcrawl = root; int =0, index=0; bool flag = false; if(root){ while(prefix[i] != '\0') { index = ((int) (prefix[i]) - (int)'a'); if(pcrawl->children[index] == null){ flag = false; return flag; } else flag = true; pcrawl = pcrawl->children[index]; i++; } } return flag; } /** deallocates memory allocated trienode. */ void triefree(struct trienode* root) { if(root){ for(int = 0; <=26; ++) { triefree(root->children[i]); } free(root); } } // trie object instantiated , called such: // struct trienode* node = triecreate(); // insert(node, "somestring"); // search(node, "key"); // triefree(node);
Comments
Post a Comment