辞書内の最長単語
Coddyの「トライ木 - データ構造シリーズ #8」コースのレッスン 13/14。
単語の辞書が与えられたとき、辞書にある単語に1文字ずつ追加していくことで構築できる最も長い単語を見つけてください。"world" は、"w"、"wo"、"wor"、および "worl" がすべて辞書に保存されている場合にのみカウントされます。
これはトライ木（trie）に最適です。すべての単語を挿入し、ルートからDFS（深さ優先探索）を行いますが、isEndOfWord とマークされている子ノードにのみ進みます。そうすることで、DFS中に訪問するすべてのノードは、すべての接頭辞がそれ自体単語であるパスを表すことになります。
最長のパスを追跡します。2つのパスが同じ長さの場合は、辞書順で小さい方を選択します。
チャレンジ
中級文字列の配列 words を受け取り、配列内のより短い単語に1文字ずつ追加していくことで構築できる最も長い単語を返す関数 longestWordInDict を作成してください。
2つの単語が同じ長さで並んだ場合は、辞書順で小さい方を返してください。配列が空の場合は、空の文字列を返してください。
必ず Trie クラスを使用してください（trienode と共に trie で提供されています）。カウントや追跡のために、セット、辞書、マップなどの言語組み込み機能を使用しないでください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line[4096];
if (!fgets(line, sizeof(line), stdin)) line[0] = 0;
line[strcspn(line, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(line, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
char* res = longestWordInDict(words, n);
printf("%s\n", res);
free(res);
return 0;
}