My solution in C, O(n)


  • 0
    J
    struct TrieNode {
    	struct TrieNode * next[26]; // a - z
    	int nword;
    	int nstart;
    };
    
    /** Initialize your data structure here. */
    struct TrieNode* trieCreate() {
    	struct TrieNode* ret = malloc(sizeof(struct TrieNode));
    	memset(ret->next, 0, sizeof(struct TrieNode*) * 26);
    	ret->nword = 0;
    	ret->nstart = 0;
    	return ret;
    }
    
    /** Inserts a word into the trie. */
    void insert(struct TrieNode* root, char* word) {
    	if (root == NULL) return;
    	struct TrieNode* p = root;
    	for (int i = 0; i < strlen(word); ++i){
    		if (p->next[word[i] - 'a'] == NULL)
    			p->next[word[i] - 'a'] = trieCreate();
    		p = p->next[word[i] - 'a'];
    		(p->nstart)++;
    	}
    	(p->nword)++;
    }
    
    /** Returns if the word is in the trie. */
    bool search(struct TrieNode* root, char* word) {
    	if (word == NULL) return true;
    	if (root == NULL) return false;
    	struct TrieNode* p = root;
    	for (int i = 0; i < strlen(word); ++i){
    		if (p->next[word[i] - 'a'] == NULL)
    			return false;
    		p = p->next[word[i] - 'a'];
    	}
    	return p->nword > 0;
    }
    
    /** Returns if there is any word in the trie
    that starts with the given prefix. */
    bool startsWith(struct TrieNode* root, char* prefix) {
    	if (prefix == NULL) return true;
    	if (root == NULL) return false;
    	struct TrieNode* p = root;
    	for (int i = 0; i < strlen(prefix); ++i){
    		if (p->next[prefix[i] - 'a'] == NULL)
    			return false;
    		p = p->next[prefix[i] - 'a'];
    	}
    	return p->nstart > 0;
    }
    
    /** Deallocates memory previously allocated for the TrieNode. */
    void trieFree(struct TrieNode* root) {
    	if (root == NULL) return;
    	for (int i = 0; i < 26; ++i)
    		free(root->next[i]);
    	free(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.