Start learning →

‹ Practice problems Easy C

Word or prefix?

Look up text in a trie and say whether it is a stored word, only the start of one, or neither.

What to build

A trie lookup with three possible answers.

Requirements

  • Insert the given words into a trie. The starter's insert does this.
  • Print word when the text is one of the stored words.
  • Print prefix when it is not a stored word, but at least one stored word starts with it.
  • Print none otherwise.

Input

The first line has n, and the second has the n words. The third line has q, and the fourth has the q texts to look up. Each has 1 to 20 lowercase letters.

Output

One line for each text.

Constraints

1 ≤ n ≤ 50 and 1 ≤ q ≤ 50.

Example

Input:

3
car cat cart
4
cat ca cow cart

Output:

word
prefix
none
word

Why it works

Every node in a trie lies on the path of at least one stored word. So finishing the walk means the text is a prefix of something, and the end flag says whether it is also a whole word.

Examples

Example 1 · Input
3
car cat cart
4
cat ca cow cart
Expected output
word
prefix
none
word
Example 2 · Input
1
a
2
a b
Expected output
word
none

Hints

Hint 1

Walk down from the root one letter at a time, as search does in the lesson.

Hint 2

If a child is missing, the answer is none.

Hint 3

If the walk finishes, the end flag of the last node tells word from prefix.

Solution

Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    struct node *child[26];
    int end;
} Node;

Node *new_node(void) {
    return calloc(1, sizeof(Node));
}

void insert(Node *root, const char *word) {
    Node *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int k = word[i] - 'a';
        if (cur->child[k] == NULL) cur->child[k] = new_node();
        cur = cur->child[k];
    }
    cur->end = 1;
}

void free_trie(Node *t) {
    if (t == NULL) return;
    for (int k = 0; k < 26; k++) free_trie(t->child[k]);
    free(t);
}

int main(void) {
    int n, q;
    char word[21];
    Node *root = new_node();
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%20s", word);
        insert(root, word);
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%20s", word);
        Node *cur = root;
        for (int j = 0; word[j] != '\0' && cur != NULL; j++) {
            cur = cur->child[word[j] - 'a'];
        }
        if (cur == NULL) printf("none\n");
        else if (cur->end) printf("word\n");
        else printf("prefix\n");
    }
    free_trie(root);
    return 0;
}

Lesson: Tries: prefix trees →