オートコンプリート
Coddyの「トライ木 - データ構造シリーズ #8」コースのレッスン 12/14。
これはトライ木（trie）の典型的なユースケースです。ユーザーがこれまでに入力した内容に基づいて、その接頭辞（prefix）で始まる、保存されているすべての単語をリストアップします。接頭辞のノードまで辿ります。辿り着けない場合は、何も返しません。次に、その下のサブツリーを探索し、見つかったすべての単語を収集します。
DFS（深さ優先探索）の最中に下っていく際、通過したエッジの文字を順次追加することで、単語を段階的に構築します。isEndOfWord が true であるノードに到達するたびに、現在のパスが一致する単語の1つとなります。
チャレンジ
中級文字列の配列 words と文字列 prefix を受け取り、その配列の中から prefix で始まる単語のリストを返す関数 autocomplete を作成してください。
返されるリストは 昇順（アルファベット順） である必要があります。一致する単語がない場合は、空のリストを返してください。
Trie クラスを使用する必要があります（trienode と共に trie で提供されています）。カウントや追跡のために、セット、辞書、マップなどの言語組み込み機能を使用しないでください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}