# 208. Implement Trie (Prefix Tree)

題目：<https://leetcode.com/problems/implement-trie-prefix-tree/>

解法：實作字典樹

Python3：

class Trie:
    def __init__(self):
        self.children = dict()
        self.isWord = False

    def insert(self, word: str) -> None:
        cur = self
        for c in word:
            if c not in cur.children:
                cur.children[c] = Trie()
            cur = cur.children[c]
        cur.isWord = True

    def search(self, word: str) -> bool:
        cur = self
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.isWord

    def startsWith(self, prefix: str) -> bool:
        cur = self
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

if __name__ == '__main__':
    obj = Trie()
    obj.insert('apple')
    result = obj.search('apple')
    print(result) # return True
    result = obj.search('app')
    print(result) # return False
    result = obj.startsWith('app')
    print(result) # return True
    obj.insert('app')
    result = obj.search('app')
    print(result) # return True

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct Trie{
    struct Trie* children[26];
    bool isWord;
} Trie;

Trie* trieCreate() {
    Trie* obj = (Trie*)malloc(sizeof(Trie));
    for (int i = 0; i < 26; i++)
        obj->children[i] = NULL;
    obj->isWord = false;
    return obj;
}

void trieInsert(Trie* obj, char * word) {
    Trie* cur = obj;
    for (int i = 0; i < strlen(word); i++) {
        int idx = word[i]-'a';
        if (cur->children[idx] == NULL)
            cur->children[idx] = trieCreate();
        cur = cur->children[idx];
    }
    cur->isWord = true;
}

bool trieSearch(Trie* obj, char * word) {
    Trie* cur = obj;
    for (int i = 0; i < strlen(word); i++) {
        int idx = word[i]-'a';
        if (cur->children[idx] == NULL)
            return false;
        cur = cur->children[idx];
    }
    return cur->isWord;
}

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

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

int main()
{
    bool result;
    Trie* obj = trieCreate();
    trieInsert(obj, "apple");
    result = trieSearch(obj, "apple");
    printf("%s\n", result ? "True" : "False"); // return True
    result = trieSearch(obj, "app");
    printf("%s\n", result ? "True" : "False"); // return False
    result = trieStartsWith(obj, "app");
    printf("%s\n", result ? "True" : "False"); // return True
    trieInsert(obj, "app");
    result = trieSearch(obj, "app");
    printf("%s\n", result ? "True" : "False"); // return True
    trieFree(obj);
}

###### tags: `leetcode` `trie`