Suggest every stored word that begins with what has been typed so far.
What to build
A trie search that lists the words below a prefix in alphabetical order.
Requirements
- Insert the given words into a trie. A word given twice is stored once.
- Print every stored word that starts with the prefix, one on each line, in alphabetical order.
- Print
noneif no stored word starts with the prefix.
Input
The first line has n, and the second has the n words. The third line has the prefix. Each has 1 to 20 lowercase letters.
Output
The matching words, one on each line, or none.
Constraints
1 ≤ n ≤ 50.
Example
Input:
5
car cat cart dog do
ca
Output:
car
cart
cat
Why it works
All the words that share a prefix live in the subtree below the prefix's node. Visiting children from a to z, and printing a node's own word before its children, gives alphabetical order with no sorting.
Examples
5 car cat cart dog do ca
car cart cat
2 sun moon x
none
Hints
Hint 1
First walk down to the node where the prefix ends, copying its letters into a buffer.
Hint 2
From that node, write a recursive function: if the node ends a word, print the buffer, then visit each child from a to z.
Hint 3
Before visiting child k, put the letter 'a' + k into the buffer at the current depth.
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 print_words(Node *t, char *buffer, int depth) {
if (t->end) {
buffer[depth] = '\0';
printf("%s\n", buffer);
}
for (int k = 0; k < 26; k++) {
if (t->child[k] != NULL) {
buffer[depth] = (char)('a' + k);
print_words(t->child[k], buffer, depth + 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;
char word[21], buffer[21];
Node *root = new_node();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%20s", word);
insert(root, word);
}
scanf("%20s", word); /* the prefix */
Node *cur = root;
int depth = 0;
while (word[depth] != '\0' && cur != NULL) {
buffer[depth] = word[depth];
cur = cur->child[word[depth] - 'a'];
depth++;
}
if (cur == NULL) printf("none\n");
else print_words(cur, buffer, depth);
free_trie(root);
return 0;
}