字典树trie-tree纯c语言leetcode实现模板

leetcode c语言trie树前缀实现

应对leetcode大部分字符串快速查找,插入,前缀匹配

该模板方便leetcode后续做题

前缀树主要是通过共享前缀的方式,保证大部分拥有共同前缀的字符串能够方便的被找到,查询。

#define N 27

struct Trie{
    struct Trie *ch[N];
    bool is_end;
};

typedef struct Trie Trie;

/** Initialize your data structure here. */

Trie* trieCreate() {
    Trie *trie = NULL;

    trie = calloc(1, sizeof(Trie));
    return trie;
}

/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {
    struct Trie *next = NULL;
    int len = strlen(word);
    int i;
    int idx;

    if (obj == NULL) {
        return;
    }

    for (i = 0; i < len; i++) {
        idx = word[i] - 'a';
        if (obj->ch[idx] == NULL) {
            obj->ch[idx] = calloc(1, sizeof(Trie));
        }
        obj = obj->ch[idx];
    }
    obj->is_end = true;
}

/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {
    int len = strlen(word);
    int i;
    int idx;

    if (obj == NULL) {
        return false;
    }

    for (i = 0; i < len; i++) {
        idx = word[i] - 'a';
        if (obj->ch[idx] == NULL) {
            return false;
        }
        obj = obj->ch[idx];
    }

    if (obj->is_end) {
        return true;
    }
    return false;
}

/** 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);
    int i;
    int idx;

    if (obj == NULL) {
        return false;
    }

    for (i = 0; i < len; i++) {
        idx = prefix[i] - 'a';
        if (obj->ch[idx] == NULL) {
            return false;
        }
        obj = obj->ch[idx];
    }

    return true;
}

void trieFree(Trie* obj) {
    int i;

    if (obj == NULL) {
        return;
    }

    for (i = 0; i < N; i++) {
        if (obj->ch[i] != NULL) {
            trieFree(obj->ch[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);
*/

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:字典树trie-tree纯c语言leetcode实现模板

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/223.html

相关文章