単語の分割
Coddyの「トライ木 - データ構造シリーズ #8」コースのレッスン 14/14。
文字列 s と単語の辞書が与えられたとき、s を余りが出ないように辞書にある単語のシーケンスに分割できるでしょうか？ "leetcode" は、両方の単語が辞書にあれば "leet" + "code" と分割できます。一方、"catsandog" はどのように切っても分割できません。
動的計画法（DP）を使えば解決できます。dp[i] を 最初の i 文字を分割できるか？ と定義します。dp[0] = true から始めます。dp[i] が true であるすべての i について、文字列の i 番目の位置からトライ木を探索します。探索がインデックス j で isEndOfWord ノードに到達するたびに、dp[j+1] = true と設定します。
トライ木を使うことで各探索が高速になります。文字が1つでも欠けていれば探索は終了します。最終的な答えは dp[n] に格納されます。
チャレンジ
中級文字列 s と文字列の配列 dictionary を受け取り、s を辞書に含まれる1つ以上の空白を含まない断片に分割できる場合は true を、そうでない場合は false を返す関数 wordBreak を作成してください。
空の s は常に分割可能です。
Trie クラスを使用する必要があります（trienode と共に trie 内で提供されています）。カウントや追跡のために、セット、辞書、マップなどの言語標準機能を使用しないでください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}