历史题目复盘：给一堆单词，能不能拼出目标串

图 1：本文封面，问题本质是「序列分段」。

先说明属性：这是一篇历史题目复盘，题目出自本地历史面试资料，与任何公司的当前招聘无关。题面很短：给定 hell、well、hello、world 这样一组单词，问能否拼出 helloworld，要求代码实现。默认规则沿用经典版本：词典里的单词可以重复使用。这道题的真正考点是——你能不能把「拼」这个动作翻译成「分段判定」。

第一步，把问题翻译成判定语言。

「能否拼出」不问怎么拼、不问几种拼法，只问行不行——这是一个布尔可达性问题。定义 dp[i] 表示目标串前 i 个字符能否由词典拼出，那么 dp[0] 为真（空前缀不需要任何单词），转移方程是：存在一个切点 j，使得 dp[j] 为真且第 j 到 i 这一段恰好是词典里的词，dp[i] 就为真。最终答案就是 dp[n]。注意它和计数型动态规划的区别：这里只要「存在一个 j」就 break，不需要枚举所有拼法。

第二步，回溯写法与记忆化。

面试官常追问「不用 DP 数组行不行」。回溯更直觉：从位置 0 开始，枚举下一个切点，切出的词在词典里就递归往下走，走不通就回退。问题在于重复子问题——对「aaaa…ab」这种必然失败的串，纯回溯会把每个位置的失败反复重算，调用次数指数爆炸。解法是给回溯加一张记忆表：把「从位置 i 开始不可行」这个结论记下来，下次直接查表。记忆化回溯和 DP 本质上是同一个状态空间的两种遍历顺序。

第三步，写出可运行代码并实测。

下面这份实现包含 DP、记忆化回溯、纯回溯三个版本，用 Node.js 22.15.0 直接运行（node word-break.js）即可：

'use strict';

// 单词拆分：判断 s 能否由词典中的单词拼接而成（词典单词可重复使用）
// 写法一：动态规划。dp[i] 表示前 i 个字符能否拼出
function wordBreakDP(s, dict) {
  const words = new Set(dict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // 空前缀总是「能拼出」
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) { dp[i] = true; break; }
    }
  }
  return dp[n];
}

// 写法二：回溯 + 记忆化。memo[i] 记录「从位置 i 开始是否可行」
function wordBreakBacktrack(s, dict) {
  const words = new Set(dict);
  const memo = new Map();
  function dfs(start) {
    if (start === s.length) return true;      // 走到末尾：拼完了
    if (memo.has(start)) return memo.get(start); // 查表，重复子问题不再重算
    for (let end = start + 1; end <= s.length; end++) {
      if (words.has(s.slice(start, end)) && dfs(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  }
  return dfs(0);
}

// 顺带演示：纯回溯（不记忆化）在长串上的指数级代价
function wordBreakNaive(s, dict) {
  const words = new Set(dict);
  let calls = 0;
  function dfs(start) {
    calls++;
    if (start === s.length) return true;
    for (let end = start + 1; end <= s.length; end++) {
      if (words.has(s.slice(start, end)) && dfs(end)) return true;
    }
    return false;
  }
  return { result: dfs(0), calls };
}

const dict = ['hell', 'well', 'hello', 'world'];
const cases = [
  ['helloworld', true],   // hello + world
  ['hellwell', true],     // hell + well
  ['hellowor', false],    // 差一个字母
  ['hellohelloworld', true], // 单词可重复使用
];
for (const [s, expect] of cases) {
  const r1 = wordBreakDP(s, dict);
  const r2 = wordBreakBacktrack(s, dict);
  console.log(`${s}：DP=${r1}，回溯=${r2}，预期=${expect} ${r1 === expect && r2 === expect ? '通过' : '失败'}`);
}

const hard = 'a'.repeat(24) + 'b'; // 全 a 加一个 b，词典只有 "a"、"aa"，必然失败且子问题极多
const naive = wordBreakNaive(hard, ['a', 'aa']);
const t0 = process.hrtime.bigint();
wordBreakBacktrack(hard, ['a', 'aa']);
const t1 = process.hrtime.bigint();
console.log(`棘手串（25 字符）：纯回溯调用 ${naive.calls} 次，记忆化回溯耗时 ${Number(t1 - t0) / 1e3 | 0} 微秒`);

实测输出：

helloworld：DP=true，回溯=true，预期=true 通过
hellwell：DP=true，回溯=true，预期=true 通过
hellowor：DP=false，回溯=false，预期=false 通过
hellohelloworld：DP=true，回溯=true，预期=true 通过
棘手串（25 字符）：纯回溯调用 196417 次，记忆化回溯耗时 21 微秒

最后一行是记忆化价值的实锤：同样一个 25 字符的串，纯回溯要调用近二十万次，加一张记忆表后微秒级出结果。

图 2：DP 建模与回溯写法对照，记忆化是性能分水岭。

可能的追问与易错点。

「复杂度？」两种写法都是 O(n²×L)——切点枚举 O(n²)，切片比较最坏 O(L)，L 为最长词长；空间 O(n)。「要输出一种具体拼法怎么办？」在 dp 里多记一个前驱切点，从 dp[n] 回溯重建即可。易错点集中在三处：忘记题目允许单词重复使用，把词典当成每个词只能用一次；把「能否拼出」误当成「最少几个词」，套错了模型；回溯不加记忆化，在长串用例上超时。跳出题目本身，分词器和 token 切分面对的就是同一类「序列分段」问题——理解了这道题的 DP 建模，再看分词算法会有「原来是亲戚」的感觉。你刷题时在「单词能不能复用」这个前提上吃过亏吗？欢迎分享。