Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 208. Implement Trie (Prefix Tree)

---

參考資訊：
https://algo.monster/liteproblems/208
https://www.cnblogs.com/grandyang/p/4491665.html

題目：


方法：


解答：

#define MAX_BUF 26

typedef struct _Trie {
    bool is_word;
    struct _Trie *child[MAX_BUF];
} Trie;

Trie* trieCreate()
{
    Trie *r = calloc(1, sizeof(Trie));

    return r;
}

void trieInsert(Trie *obj, char *word)
{
    int i = 0;
    int len = strlen(word);
    Trie *p = obj;

    for (i = 0; i < len; i++) {
        char ch = word[i] - 'a';

        if (p->child[ch] == NULL) {
            p->child[ch] = calloc(1, sizeof(Trie));
        }
        p = p->child[ch];
    }
    p->is_word = true;
}

bool trieSearch(Trie *obj, char *word)
{
    int i = 0;
    int len = strlen(word);
    Trie *p = obj;

    for (i = 0; i < len; i++) {
        char ch = word[i] - 'a';

        if (p->child[ch] == NULL) {
            return false;
        }
        p = p->child[ch];
    }
    return p->is_word;
}

bool trieStartsWith(Trie *obj, char *prefix)
{
    int i = 0;
    int len = strlen(prefix);
    Trie *p = obj;

    for (i = 0; i < len; i++) {
        char ch = prefix[i] - 'a';

        if (p->child[ch] == NULL) {
            return false;
        }
        p = p->child[ch];
    }
    return true;
}

void trieFree(Trie *obj)
{
    int i = 0;
    Trie *p = obj;

    for (i = 0; i < MAX_BUF; i++) {
        if (p->child[i]) {
            trieFree(p->child[i]);
            p->child[i] = NULL;
        }
    }
    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);
*/