力扣208.实现Trie(前缀树)

力扣208.实现Trie(前缀树)

图中蓝色表示在该路径中有单词以它作为结尾

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);
*/
上一篇:Leetcode 528


下一篇:不要62 HDU2089