LeetCodeTrie字典树

基础：通过树的结构实现一个进行字符串反复查询的结构：

相关教程：https://leetcode-cn.com/problems/short-encoding-of-words/solution/99-java-trie-tu-xie-gong-lue-bao-jiao-bao-hui-by-s/

208. 实现 Trie (前缀树) https://leetcode-cn.com/problems/implement-trie-prefix-tree/

typedef struct Trie{
    struct Trie * children[26];
    int isEnd;
    
} Trie;

/** Initialize your data structure here. */

Trie* trieCreate() {
    Trie *node = (Trie *)malloc(sizeof(Trie));
    memset(node->children, 0, sizeof(node->children));
    node->isEnd = false;
    return node;
}

/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {
    int len = strlen(word);
    for (int i = 0;i < len;++i) {
        int ch = word[i] - 'a';
        if (obj->children[ch] == NULL) {
            obj->children[ch] = trieCreate();
        }
        obj = obj->children[ch];
    }
    obj->isEnd = true;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {
    int len = strlen(word);
    for (int i = 0;i < len;++i) {
        int ch = word[i] - 'a';
        if (obj->children[ch] == NULL) {
            return false;
        }
        obj = obj->children[ch];
    }
    return obj->isEnd;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {
    int len = strlen(prefix);
    for (int i = 0;i < len;++i) {
        int ch = prefix[i] - 'a';
        if (obj->children[ch] == NULL) {
            return false;
        }
        obj = obj->children[ch];
    }
    return true;
}

void trieFree(Trie* obj) {
    for (int i = 0;i < 26;++i) {
        if (obj->children[i] != NULL) {
            trieFree(obj->children[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);
*/

相关练习：

648. 单词替换 https://leetcode-cn.com/problems/replace-words/

820. 单词的压缩编码 https://leetcode-cn.com/problems/short-encoding-of-words/

677. 键值映射 https://leetcode-cn.com/problems/map-sum-pairs/