[LeetCode 208] Implement Trie (Prefix Tree) [C] [Runtime : 39 MS]

1. Runtime Distribution

2. Submission Details

3. Description

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

4. Code

Code

typedef struct Trie {
    char letter;
    struct Trie *child;
    struct Trie *next;
    bool is_leaf;
} Trie;

Trie* trieCreate() {
    Trie *p = (Trie *)malloc(sizeof(Trie));
    p->child = NULL;
    p->next = NULL;
    p->is_leaf = false;
    return p;
}

static void diff(Trie *trie, char *word, Trie **diff_trie, Trie ***child_end, char **diff_word) {
    char *s = word;
    Trie **child = &trie->child;

    while (*child != NULL && *s != '\0') 
    {
        if (*s == (*child)->letter) {
            diff(*child, ++s, diff_trie, child_end, diff_word);
            return;
        }
        child = &(*child)->next;
    }

    if (diff_trie)
    {
        *diff_trie = trie;
    }

    if (child_end)
    {
        *child_end = child;
    }

    if (diff_word)
    {
        *diff_word = s;
    }
}

void trieInsert(Trie* trie, char* word) {
    Trie *diff_trie;
    Trie **child_end;
    char *diff_word;

    diff(trie, word, &diff_trie, &child_end, &diff_word);
    char *s = diff_word;
    Trie *leaf = diff_trie;
    while (*s != '\0') 
    {
        *child_end = trieCreate();
        leaf = *child_end;
        leaf->letter = *s++;
        child_end = &leaf->child;
    }
    leaf->is_leaf = true;
}

bool trieSearch(Trie* trie, char* word) {
    Trie *diff_trie;
    char *diff_word;
    diff(trie, word, &diff_trie, NULL, &diff_word);
    return diff_trie->is_leaf && *diff_word == '\0';
}

bool trieStartsWith(Trie* trie, char* prefix) {
    Trie *diff_trie;
    char *diff_word;
    diff(trie, prefix, &diff_trie, NULL, &diff_word);
    return *diff_word == '\0';
}

void trieFree(Trie* trie) {
    if (trie->child == NULL && trie->next == NULL) {
        free(trie);
        return;
    }

    if (trie->child)
    {
        trieFree(trie->child);
    }

    if (trie->next)
    {
        trieFree(trie->next);
    }
}

Test

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

typedef struct Trie {
    char letter;
    struct Trie *child;
    struct Trie *next;
    bool is_leaf;
} Trie;

Trie* trieCreate() {
    Trie *p = (Trie *)malloc(sizeof(Trie));
    p->child = NULL;
    p->next = NULL;
    p->is_leaf = false;
    return p;
}

static void diff(Trie *trie, char *word, Trie **diff_trie, Trie ***child_end, char **diff_word) {
    char *s = word;
    Trie **child = &trie->child;

    while (*child != NULL && *s != '\0') 
    {
        if (*s == (*child)->letter) {
            diff(*child, ++s, diff_trie, child_end, diff_word);
            return;
        }
        child = &(*child)->next;
    }

    if (diff_trie)
    {
        *diff_trie = trie;
    }

    if (child_end)
    {
        *child_end = child;
    }

    if (diff_word)
    {
        *diff_word = s;
    }
}

void trieInsert(Trie* trie, char* word) {
    Trie *diff_trie;
    Trie **child_end;
    char *diff_word;

    diff(trie, word, &diff_trie, &child_end, &diff_word);
    char *s = diff_word;
    Trie *leaf = diff_trie;
    while (*s != '\0') 
    {
        *child_end = trieCreate();
        leaf = *child_end;
        leaf->letter = *s++;
        child_end = &leaf->child;
    }
    leaf->is_leaf = true;
}

bool trieSearch(Trie* trie, char* word) {
    Trie *diff_trie;
    char *diff_word;
    diff(trie, word, &diff_trie, NULL, &diff_word);
    return diff_trie->is_leaf && *diff_word == '\0';
}

bool trieStartsWith(Trie* trie, char* prefix) {
    Trie *diff_trie;
    char *diff_word;
    diff(trie, prefix, &diff_trie, NULL, &diff_word);
    return *diff_word == '\0';
}

void trieFree(Trie* trie) {
    if (trie->child == NULL && trie->next == NULL) {
        free(trie);
        return;
    }

    if (trie->child)
    {
        trieFree(trie->child);
    }

    if (trie->next)
    {
        trieFree(trie->next);
    }
}

int main() {

    Trie* node = trieCreate();

    assert(trieSearch(node, "some") == false);
    trieInsert(node, "s");
    assert(trieSearch(node, "some") == false);
    assert(trieSearch(node, "s") == true);

    trieInsert(node, "some");
    assert(trieSearch(node, "some") == true);

    trieInsert(node, "somestring");
    trieInsert(node, "someword");
    trieInsert(node, "word");

    assert(trieSearch(node, "word") == true);
    assert(trieSearch(node, "somestring") == true);
    assert(trieSearch(node, "someword") == true);
    assert(trieSearch(node, "somew") == false);
    assert(trieSearch(node, "somes") == false);
    assert(trieSearch(node, "somex") == false);

    assert(trieStartsWith(node, "some") == true);
    assert(trieStartsWith(node, "somew") == true);
    assert(trieStartsWith(node, "somes") == true);
    assert(trieStartsWith(node, "somex") == false);

    trieFree(node);

    printf("all tests passed!\n");

    system("pause");
    return 0;
}