C language · prefix tree implementation

Trie（ It sounds like "try"） Or say Prefix tree It's a tree data structure , Keys for efficient storage and retrieval of string datasets . This data structure has quite a number of application scenarios , For example, automatic completion and spelling check .Trie Also known as prefix tree or dictionary tree , It's a tree with roots , Each of its nodes contains the following fields ：

         An array of pointers to child nodes next.
         Boolean fields isEnd, Indicates whether the node is the end of the string

typedef struct Trie{
    bool isEnd; // Whether the node is the end of a string 
    struct Trie * next[26]; // The alphabet 
}Trie;

Initialize the tree node  

For each tree node to be inserted , Need to save isEnd Is string is end , And for the next Array points to NULL

/* false： It's not over   true： End of the said */
Trie* trieCreate() {
    Trie * obj = malloc(sizeof(Trie) * 1);
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->isEnd = false;
    return obj;
}

Insert string

Let's start at the root of the dictionary tree , Insert string . For the child node corresponding to the current character , There are two situations ：

Child nodes exist . Move along the pointer to the child node , Continue processing the next character .
Child node does not exist . Create a new child node , Recorded in the children The corresponding position of the array , Then move along the pointer to the child node , Continue searching for the next character .

Repeat the above steps , Until the last character of the string is processed , Then mark the current node as the end of the string .

/*
*void trieInsert(Trie* obj, char * word)
void trieInsert： Insert string before infix 
Trie* obj： Prefix tree head node 
char * word： character string 
 Return value ： nothing 
*/
void trieInsert(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            Trie * objNode = trieCreate();
            obj->next[(word[i]-'a')] = objNode;
        }
        obj = obj->next[(word[i]-'a')];
    }
    obj->isEnd = true;
}

Find prefix

Let's start at the root of the dictionary tree , Find prefix . For the child node corresponding to the current character , There are two situations ：

Child nodes exist . Move along the pointer to the child node , Continue searching for the next character .
Child node does not exist . Description the prefix... Is not included in the dictionary tree , Return 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 , This indicates that the prefix exists in the dictionary tree . Besides , If the corresponding node at the end of the prefix isEnd It's true , It indicates that the string exists in the dictionary tree .

/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch： Check string word Whether it is on the prefix tree 
Trie* obj： Prefix tree head node 
char * word: character string 
 Return value ： There is returned true
         There is no return false
*/
bool trieSearch(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            return false;
        }
        obj = obj->next[(word[i]-'a')];
    }
    if(obj->isEnd == false)
    {
        return false;
    }
    return true;
}

The destruction  

For prefix trees that already exist , Recursive destruction is more convenient

void trieFree(Trie* obj) {
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
            trieFree(obj->next[i]);
    }
    free(obj);
}

Concrete realization  

typedef struct Trie{
    bool isEnd; // Whether the node is the end of a string 
    struct Trie * next[26]; // The alphabet 
}Trie;

/* false： It's not over   true： End of the said */
Trie* trieCreate() {
    Trie * obj = malloc(sizeof(Trie) * 1);
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->isEnd = false;
    return obj;
}
/*
*void trieInsert(Trie* obj, char * word)
void trieInsert： Insert string before infix 
Trie* obj： Prefix tree head node 
char * word： character string 
 Return value ： nothing 
*/
void trieInsert(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            Trie * objNode = trieCreate();
            obj->next[(word[i]-'a')] = objNode;
        }
        obj = obj->next[(word[i]-'a')];
    }
    obj->isEnd = true;
}
/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch： Check string word Whether it is on the prefix tree 
Trie* obj： Prefix tree head node 
char * word: character string 
 Return value ： There is returned true
         There is no return false
*/
bool trieSearch(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            return false;
        }
        obj = obj->next[(word[i]-'a')];
    }
    if(obj->isEnd == false)
    {
        return false;
    }
    return true;
}

bool trieStartsWith(Trie* obj, char * prefix) {
    int len = strlen(prefix);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(prefix[i]-'a')] == NULL)
        {
            return false;
        }
        obj = obj->next[(prefix[i]-'a')];
    }
    return true;
}

void trieFree(Trie* obj) {
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
            trieFree(obj->next[i]);
    }
    free(obj);
}

/**
 * Your Trie struct will be instantiated and called as such:
 * Trie* obj = trieCreate();
 * trieInsert(obj, word);
 
 * bool param_2 = trieSearch(obj, word);
 
 * bool param_3 = trieStartsWith(obj, prefix);
 
 * trieFree(obj);
*/

practice 1          Force to buckle 208 topic

Power button https://leetcode.cn/problems/implement-trie-prefix-tree/

Reference link  

http://t.csdn.cn/2UBpShttp://t.csdn.cn/2UBpS Ideas

Prefix ： The prefix of a string refers to any header of the string . Like strings “abbc” The prefix of is “a”,“ab”,“abb”,“abbc”.
Prefix tree ： Prefix tree is a multi tree structure for fast retrieval , Use the common prefix of string to reduce the query time , The core idea is space for time , It is often used by search engines for text word frequency statistics .
Each node represents the node of a tree , Then the nodes of each tree can point to 26 Child node , In this way, we can build a string tree

Implementation code

typedef struct Trie{
    bool isEnd; // Whether the node is the end of a string 
    struct Trie * next[26]; // The alphabet 
}Trie;

/* false： It's not over   true： End of the said */
Trie* trieCreate() {
    Trie * obj = malloc(sizeof(Trie) * 1);
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->isEnd = false;
    return obj;
}
/*
*void trieInsert(Trie* obj, char * word)
void trieInsert： Insert string before infix 
Trie* obj： Prefix tree head node 
char * word： character string 
 Return value ： nothing 
*/
void trieInsert(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            Trie * objNode = trieCreate();
            obj->next[(word[i]-'a')] = objNode;
        }
        obj = obj->next[(word[i]-'a')];
    }
    obj->isEnd = true;
}
/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch： Check string word Whether it is on the prefix tree 
Trie* obj： Prefix tree head node 
char * word: character string 
 Return value ： There is returned true
         There is no return false
*/
bool trieSearch(Trie* obj, char * word) {
    int len = strlen(word);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(word[i]-'a')] == NULL)
        {
            return false;
        }
        obj = obj->next[(word[i]-'a')];
    }
    if(obj->isEnd == false)
    {
        return false;
    }
    return true;
}

bool trieStartsWith(Trie* obj, char * prefix) {
    int len = strlen(prefix);
    for(int i = 0; i < len; i++)
    {
        if(obj->next[(prefix[i]-'a')] == NULL)
        {
            return false;
        }
        obj = obj->next[(prefix[i]-'a')];
    }
    return true;
}

void trieFree(Trie* obj) {
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
            trieFree(obj->next[i]);
    }
    free(obj);
}

/**
 * Your Trie struct will be instantiated and called as such:
 * Trie* obj = trieCreate();
 * trieInsert(obj, word);
 
 * bool param_2 = trieSearch(obj, word);
 
 * bool param_3 = trieStartsWith(obj, prefix);
 
 * trieFree(obj);
*/

practice 2          Force to buckle 648 topic
Power button https://leetcode.cn/problems/replace-words/

  Reference link

http://t.csdn.cn/aKq0zhttp://t.csdn.cn/aKq0z Ideas

Prefix ： The prefix of a string refers to any header of the string . Like strings “abbc” The prefix of is “a”,“ab”,“abb”,“abbc”.
Prefix tree ： Prefix tree is a multi tree structure for fast retrieval , Use the common prefix of string to reduce the query time , The core idea is space for time , It is often used by search engines for text word frequency statistics . Prefix trees are often used for strings .
Ideas
Put this question dictionary Convert to prefix tree , Then on sentence Traverse , Determine whether the string prefix is on the tree , Simplify the output if it exists , If it doesn't exist, it will be completely output , The last defined string links the comparison results of all results
The following code can also be optimized

Implementation code

//0： end ,1： There is no end 
typedef struct word{
    int end;
    struct word * next[26];
}word;

// Initialize prefix tree 
word * trieCreate(){
    word * obj = malloc(sizeof(word) * 1);
    for(int i = 0; i < 26; i++)
    {
        obj->next[i] = NULL;
    }
    obj->end = 0;;
    return obj;
}
/*
*void word_create(word * root, char ** dictionary, int inode)
void word_create： Insert string before infix 
word * root： Prefix tree head node 
char ** dictionary： character string 
int inod： String line subscript 
 Return value ： nothing 
*/
void word_create(word * root, char ** dictionary, int inode)
{
    int len = strlen(dictionary[inode]);
    for(int i = 0; i < len; i++)
    {
        if(root->next[dictionary[inode][i] - 'a'] == NULL)
        {
            word * n = trieCreate();
            root->next[dictionary[inode][i] - 'a'] = n;
        }
        root = root->next[dictionary[inode][i] - 'a'];
    }
    root->end = 1;
}
// Determine whether the string is on the prefix tree 
char * str_if(word * root, char * sentence, int len_left, int len_right)
{
    int len = 0;
    for(int i = len_left; i < len_right; i++)
    {
        if(root->next[sentence[i] - 'a'] && root->end == 0)
        {
            len++;
            root = root->next[sentence[i] - 'a'];
        }
        else
        {
            if(root->end == 0)
            {
                len = len_right - len_left;
            }
            break;
        }
    }
    if(len)
    {
        char * str = malloc(sizeof(char) * (len + 1 + 1));
        strncpy(str, sentence+len_left, len);
        str[len] = ' ';
        str[len + 1] = '\0';
        return str;
    }
    else
    {
        char * str = malloc(sizeof(char) * (len_right - len_left + 1 + 1));
        strncpy(str, sentence+len_left, len_right - len_left);
        str[len_right - len_left] = ' ';
        str[len_right - len_left + 1] = '\0';
        return str;
    }
    return NULL;
}
// Optimize string sentence
char * replaceWords(char ** dictionary, int dictionarySize, char * sentence){
    char * str = malloc(sizeof(char) * (1000 * 1000 + 1));
    str[0] = '\0';
    word * root = trieCreate();
    for(int i = 0; i < dictionarySize; i++)
    {   
        word_create(root, dictionary, i);
    }
    int len = strlen(sentence);
    int len_left = 0;
    int i;
    for(i = 0; i < len; i++)
    {
        if(sentence[i] == ' ')
        {
            strcat(str , str_if(root, sentence, len_left, i));

            len_left = i+1;
        }
    }
    strcat(str , str_if(root, sentence, len_left, i));
    len = strlen(str);
    str[len - 1] = '\0';
    trieFree(root);
    return str;
}
// Destroy prefix tree 
void trieFree(word * obj) {
    for(int i = 0; i < 26; i++)
    {
        if(obj->next[i])
            trieFree(obj->next[i]);
    }
    free(obj);
}