[208] Implement Trie (Prefix Tree)

最終還是寫了個字典樹

一開始的 isEnd 初始值想錯了，卡住老半天Orz

因為可能有 app跟 apple 都被加進去，要小心app本來設成 isEnd true了，

在加apple 進去時可能會被洗掉，所以各種卡住Orz

寫完的心得是，還好沒叫我考慮delete = =+

感覺麻煩 XD

typedef struct {

struct Trie* next[26];

bool isEnd;

} Trie;

Trie* trieCreate() {

Trie* node=malloc (sizeof(Trie));

node->isEnd=false;

for (int i=0;i<26;i++)

node->next[i]=NULL;

return node;

}

void trieInsert(Trie* obj, char * word) {

int len = strlen(word);

for (int i=0;i<len;i++)

{

if (obj->next[word[i]-'a']== NULL)

obj->next[word[i]-'a'] = trieCreate();

obj = obj->next[word[i]-'a'];

}

obj->isEnd=true;

}

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;

else

obj = obj->next[word[i]-'a'];

}

return (obj->isEnd)? true : false;

}

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;

else

obj = obj->next[prefix[i]-'a'];

}

return true;

}

void trieFree(Trie* obj) {

for (int i=0;i<26;i++)

{

if (obj->next[i]!= NULL)

trieFree(obj->next[i]);

}

free(obj);

return;

}

/**

* 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);

*/