Leetcode[300. Implement Trie] - prefix tree

Title:

Trie (pronounced like "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in string data sets. This data structure has many application scenarios, such as automatic completion and spell checking.

Please implement the Trie class:

Trie() Initializes the prefix tree object.
void insert(String word) Inserts a string into the tree word . 
boolean search(String word) If string word In the prefix tree, return true(That is, it has been inserted before retrieval); Otherwise, return false . 
boolean startsWith(String prefix) If you have previously inserted a string word One of the prefixes is prefix ，return true ；Otherwise, return false . 

Example:

input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
output
[null, null, true, false, true, null, true]

explain
Trie trie = new Trie();
trie.insert("apple");
trie.search(“apple”); // Return True
trie.search(“app”); // Return False
trie.startsWith(“app”); // Return True
trie.insert("app");
trie.search(“app”); // Return True

Tips:

1 <= word.length, prefix.length <= 2000
word and prefix Composed of lowercase English letters only
insert,search and startsWith The total number of calls shall not exceed 3 * 10**4 second

Method: dictionary tree

Trie, also known as prefix tree or dictionary tree, is a rooted tree. Each node of trie contains the following fields:

Pointer array children pointing to child nodes. For this question, the length of the array is 26, that is, the number of lowercase English letters. At this time, children[0] corresponds to lowercase letter a, children[1] corresponds to lowercase letter b,..., and children[25] corresponds to lowercase letter z.
Boolean field isEnd, indicating whether the node is the end of the string.

Insert string
We start at the root of the dictionary tree and insert a string. For the child node corresponding to the current character, there are two cases:

Child nodes exist. Move along the pointer to the child node and continue processing the next character.
Child node does not exist. Create a new child node, record it in the corresponding position of the children array, and then move along the pointer to the child node to continue searching for the next character.

Repeat the above steps until the last character of the string is processed, and then mark the current node as the end of the string.
Find prefix
We start at the root of the dictionary tree and look for the prefix. For the child node corresponding to the current character, there are two cases:

Child nodes exist. Move the pointer to the child node and continue searching for the next character.
Child node does not exist. Description the dictionary tree does not contain this prefix and returns a null pointer.

Repeat the above steps until the null pointer is returned or the last character of the prefix is searched.
If the search reaches the end of the prefix, it indicates that the prefix exists in the dictionary tree. In addition, if the isEnd of the corresponding node at the end of the prefix is true, it indicates that the string exists in the dictionary tree.

Demo video:

https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shu-ju-jie-gou-he-suan-fa-zi-dian-shu-de-6t43/

typedef struct Trie
{
    struct Trie* children[26];
    int isEnd;
}Trie;
Trie* trieCreate()
{
    Trie*ret=(Trie*)malloc(sizeof(Trie));
    memset(ret->children,0,sizeof(ret->children));
    ret->isEnd=0;
    return ret;

}
void trieInsert(Trie* obj, char* word) 
{
    int len=strlen(word);
    for(int i=0;i<len;i++)
    {
        int id=word[i]-'a';
        if(obj->children[id]==NULL)obj->children[id]=trieCreate();
        obj=obj->children[id];
    }
    obj->isEnd=1;

}
int trieSearch(Trie* obj, char* word) 
{
    int len = strlen(word);
    for (int i = 0; i < len; i++) 
    {
        int id = word[i] - 'a';
        if (obj->children[id] == NULL) return 0;
        obj = obj->children[id];
    }
    return obj->isEnd;
}
int trieStartsWith(Trie* obj, char * prefix) 
{
    int len=strlen(prefix);
    for(int i=0;i<len;i++)
    {
        int id=prefix[i]-'a';
        if(obj->children[id]==NULL)return 0;
        obj=obj->children[id];
    }
    return 1;
}
void trieFree(Trie* obj) 
{
    for(int i=0;i<26;i++)
        if(obj->children[i])trieFree(obj->children[i]);
    free(obj);
}