接頭辞を持つ単語のカウント
Coddyの「トライ木 - データ構造シリーズ #8」コースのレッスン 11/14。
指定された接頭辞で始まる格納済みの単語は何個ありますか？すべての単語を挿入した後、ルートから接頭辞に沿って1文字ずつ進みます。文字が欠けている場合、答えはゼロです。その接頭辞で始まる単語は存在し得ません。
接頭辞の終わりに到達すると、あるノードにたどり着きます。この接頭辞で始まるすべての格納済み単語は、そのノードをルートとするサブツリーのどこかに存在します。サブツリーを走査し、isEndOfWord が true であるすべてのノードに対して1を加算することで、それらをカウントします。
チャレンジ
簡単文字列の配列 words と文字列 prefix を受け取り、配列内の単語のうち、指定された接頭辞で始まる単語の数を返す関数 countWordsWithPrefix を作成してください。
空の接頭辞はすべての単語に一致します。
必ず 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"); }
printf("%d\n", countWordsWithPrefix(words, n, prefix));
return 0;
}