单词拆分
Coddy 字典树：数据结构系列第 8 课 课程的第 14 课，共 14 课。
给定一个字符串 s 和一个由单词组成的字典，我们能否把 s 拆分成一串字典中的单词，并且不剩下任何字符？如果字典中同时有 "leet" 和 "code"，那么 "leetcode" 可以拆分为 "leet" + "code"；无论怎么拆分，"catsandog" 都无法拆分。
用一次动态规划遍历就能解决问题。定义 dp[i] 表示前 i 个字符能否拆分？从 dp[0] = true 开始。对于每个满足 dp[i] 为 true 的 i，从字符串的第 i 个位置开始遍历字典树；每当遍历到索引 j 处的 isEndOfWord 节点时，就设置 dp[j+1] = true。
字典树让每次遍历都很快：遇到一个不存在的字符，遍历就会结束。最终答案保存在 dp[n] 中。
挑战
中等编写一个函数 wordBreak，它接收一个字符串 s 和一个字符串数组 dictionary。如果 s 可以拆分成一个或多个不含空白字符的片段，且每个片段都在字典中，则返回 true；否则返回 false。
空字符串 s 始终可以拆分。
你必须使用 Trie 类（在 trie 和 trienode 中提供）。不要使用语言内置的集合、字典或映射来计数或跟踪。
亲手试试
#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;
}
字典树：数据结构系列第 8 课中的所有课
自己练习： C 在线编译器