单词拆分问题如何用 Trie 优化匹配过程？

简化版

单词拆分通常用动态规划，判断字符串能否被词典里的单词拼出来。

如果每次枚举子串再去哈希表查，可能产生很多子串对象。用 Trie 可以从当前位置开始沿字符往后走，遇到单词结束节点时再更新 DP，避免无意义的子串构造。

本质是用 Trie 优化「从某个位置开始能匹配哪些词典单词」。

详细版

设 dp[i] 表示前 i 个字符能否被拆分。

当 dp[i] = true 时，从 s[i] 开始沿 Trie 向后匹配：

cur = root
for j in i..n-1:
  cur = cur.children[s[j]]
  if cur == null: break
  if cur.isEnd: dp[j + 1] = true

方法	特点
哈希表枚举子串	简单，但可能频繁创建子串
Trie 向后匹配	只沿可行前缀走，剪枝自然

如果词典单词很多、前缀共享明显，Trie 会更有优势。

完整版教学

1. 单词拆分的基础 DP

单词拆分问题通常是：给字符串 s 和词典 wordDict，判断 s 是否能由词典单词拼接而成。

经典 DP 定义：

dp[i] = s[0..i) 是否可以被拆分

初始：

dp[0] = true

如果 dp[i] = true 且 s[i..j) 是词典单词，那么 dp[j] = true。

2. 哈希表做法的问题

哈希表做法会枚举很多子串：

for i:
  for j:
    if dp[i] and s.substring(i, j) in dict:
      dp[j] = true

这很直观，但可能有两个问题：

子串枚举很多；
某些语言创建 substring 有额外成本。

Trie 的价值是把「枚举所有 j」变成「只沿词典中存在的前缀继续走」。

3. Trie 如何匹配从 i 开始的单词

先把词典全部插入 Trie。

当某个位置 i 可达，也就是 dp[i] = true 时，从 root 开始读 s[i]、s[i+1]...。

只要 Trie 中没有对应孩子，就立刻停止，因为再往后也不可能匹配任何词典单词。

if cur.children[ch] == null:
  break

4. 遇到 isEnd 为什么更新 DP

如果走到某个节点 cur.isEnd = true，说明：

s[i..j] 是一个词典单词

又因为 dp[i] = true，所以前面能拆，当前单词也能接上，于是：

dp[j + 1] = true

这样就把可达位置向后推进。

5. 伪代码完整流程

可以这样写：

buildTrie(wordDict)
dp[0] = true

for i in 0..n-1:
  if not dp[i]: continue
  cur = root
  for j in i..n-1:
    ch = s[j]
    if cur.children[ch] == null:
      break
    cur = cur.children[ch]
    if cur.isEnd:
      dp[j + 1] = true

如果最后 dp[n] = true，说明可以拆分。

6. 复杂度如何分析

最坏情况下仍可能比较多，比如词典里有很多相同前缀。

但实践中，Trie 可以通过不存在的前缀快速 break。

指标	说明
建 Trie	和词典总字符数相关
DP 匹配	和可达位置及前缀匹配长度相关
空间	Trie 节点 + `dp` 数组

如果知道最大单词长度 maxLen，还可以限制内层循环最多走 maxLen 步。

7. 能否恢复拆分方案

可以。

除了 dp，再维护前驱：

prev[j + 1] = i

或者保存所有可行前驱，用于输出所有拆分句子。

这时 Trie 仍然负责快速找从 i 开始的词典单词，DP 负责记录路径。

8. 常见误区与追问

误区：用了 Trie 就不需要 DP。 Trie 只负责匹配词典单词，是否能拼完整串仍需要状态转移。
误区：Trie 解法一定比哈希表快。 数据规模、词典前缀共享和语言 substring 成本都会影响结果。
误区：内层循环必须走到字符串末尾。 一旦 Trie 没有对应孩子就可以 break。
追问：如何输出一种拆分方案？ 维护前驱位置，最后从 n 回溯。
追问：如何输出所有方案？ 保存每个位置的所有前驱，再 DFS 组合结果。

简化版

详细版