图中蓝色表示在该路径中有单词以它作为结尾
typedef struct {
int isEnd;
struct trie* next[26];
} Trie;
Trie* trieCreate() {
Trie *root;
root = (Trie *)malloc(sizeof(Trie) * 1 );
memset(root, 0, sizeof(*root));
root->isEnd = 0;
return root;
}
void trieInsert(Trie* obj, char * word) {
Trie *node = obj;
for (int i = 0; word[i] != '\0'; i++) {
char c = word[i];
if ( node->next[c-'a'] == NULL){
node->next[c-'a'] = trieCreate();
}
node = node->next[c-'a'];
}
node->isEnd = 1;
}
bool trieSearch(Trie* obj, char * word) {
Trie *node = obj;
for (int i = 0; word[i] != '\0'; i++){
char c = word[i];
if ( node->next[c-'a'] == NULL){
return false;
}
node = node->next[c-'a'];
}
return node->isEnd > 0;
}
bool trieStartsWith(Trie* obj, char * prefix) {
Trie *node = obj;
for (int i = 0; prefix[i] != '\0'; i++){
char c = prefix[i];
if ( node->next[c-'a'] == NULL){
return false;
}
node = node->next[c-'a'];
}
return true;
}
void trieFree(Trie* obj) {
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);
*/