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

*/

[20250928] 又寫了一次字典數, 感覺到自己的退步 XDDDDDD Orz

compiler可能有改版, 在typedef 的地方要加個Trie 不然都不能用了QQ」

free的地方其實已經有回圈了(?) 所以如果不是上一次的我沒考慮清楚, （根本不知道自己在寫什麼?! = =+) 就是這一次的我退步XDDDDD

typedef struct Trie{

struct Trie* node[26];

bool end ;

} Trie;

Trie* trieCreate() {

Trie* root = calloc (1, sizeof (Trie));

root->end = false;

return root;

}

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

int len = strlen(word);

Trie* ptr = obj;

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

{

int idx = word[i]-'a';

if (ptr->node[idx]== NULL)

ptr->node[idx]= trieCreate();

ptr = ptr->node[idx];

}

ptr->end = true;

}

bool trieSearch(Trie* obj, char* word) {

int len = strlen(word);

Trie* ptr = obj;

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

{

int idx = word[i]-'a';

if (ptr->node[idx]== NULL)

return false;

ptr = ptr->node[idx];

}

return ptr->end;

}

bool trieStartsWith(Trie* obj, char* prefix) {

int len = strlen(prefix);

Trie* ptr = obj;

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

{

int idx = prefix[i]-'a';

if (ptr->node[idx]== NULL)

return false;

ptr = ptr->node[idx];

}

return true;

}

void trieFree(Trie* obj) {

// if (obj== NULL)

// return;

Trie* ptr = obj;

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

{

if (ptr->node[i]!= NULL)

trieFree(ptr->node[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);

*/