Word Break（单词拆分）

题目 / Problem

中文： 给定一个字符串 s 和一个字符串字典 wordDict，如果可以使用字典中的一个或多个单词将 s 完整拆分，返回 true；否则返回 false。

字典中的同一个单词可以在拆分过程中重复使用多次。

English: Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Otherwise, return false.

The same dictionary word may be reused multiple times in the segmentation.

示例 / Examples

Example 1

Input:  s = "leetcode", wordDict = ["leet","code"]
Output: true

"leetcode" = "leet" + "code"

Example 2

Input:  s = "applepenapple", wordDict = ["apple","pen"]
Output: true

"applepenapple" = "apple" + "pen" + "apple"

单词 "apple" 被重复使用，这是允许的。
The word "apple" is reused, which is allowed.

Example 3

Input:  s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

虽然字符串的部分前缀可以拆分，但无法用字典单词完整覆盖整个字符串。
Although some prefixes can be segmented, the dictionary cannot cover the entire string.

约束 / Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 只包含小写英文字母。
s and wordDict[i] contain only lowercase English letters.
wordDict 中的所有字符串互不相同。
All strings in wordDict are unique.

解题思路：动态规划 / Approach: Dynamic Programming

定义：
Define:

dp[i] = s 的前 i 个字符能否被字典中的单词完整拆分
dp[i] = whether the first i characters of s can be fully segmented

这里 dp[i] 对应字符串前缀 s[0...i)。
Here, dp[i] represents the prefix s[0...i).

初始状态 / Base Case

dp[0] = true;

空字符串不需要任何单词就可以完成拆分。这个状态也为第一个单词提供合法的起点。
The empty string is considered successfully segmented. This state also provides a valid starting point for the first word.

状态转移 / Transition

对于每个结束位置 end，枚举最后一个单词的起始位置 start：
For each ending position end, enumerate the starting position start of the final word:

如果 dp[start] 为 true
并且 s.slice(start, end) 存在于字典中
那么 dp[end] = true

If dp[start] is true
and s.slice(start, end) exists in the dictionary,
then dp[end] = true

用公式表示：
As a formula:

dp[end] = dp[start] && wordSet.has(s.slice(start, end))

只要找到一个合法的 start，就可以确定 dp[end] = true 并停止继续枚举。
As soon as one valid start is found, set dp[end] = true and stop checking additional splits.

为什么使用 `Set`？ / Why Use a Set?

将 wordDict 转换为 Set，可以快速判断某个子字符串是否是字典单词。
Convert wordDict into a Set to efficiently test whether a substring is a dictionary word.

const wordSet = new Set(wordDict);

如果直接在数组中查找，每次判断还需要线性扫描整个字典。
Searching the original array would require a linear scan through the dictionary for every lookup.

最长单词剪枝 / Maximum-Word-Length Pruning

设字典中最长单词的长度为 maxWordLength。最后一个单词不可能超过这个长度，因此只需要检查：
Let maxWordLength be the length of the longest dictionary word. The final word cannot be longer than this, so only check:

start >= end - maxWordLength

这样可以避免枚举明显不可能存在于字典中的过长子字符串。
This avoids examining substrings that are too long to exist in the dictionary.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const maxWordLength = Math.max(
    ...wordDict.map((word) => word.length)
  );

  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;

  for (let end = 1; end <= s.length; end++) {
    const earliestStart = Math.max(0, end - maxWordLength);

    for (let start = end - 1; start >= earliestStart; start--) {
      if (!dp[start]) {
        continue;
      }

      const word = s.slice(start, end);

      if (wordSet.has(word)) {
        dp[end] = true;
        break;
      }
    }
  }

  return dp[s.length];
}

执行过程 / Walkthrough

以 s = "leetcode"、wordDict = ["leet", "code"] 为例：
For s = "leetcode" and wordDict = ["leet", "code"]:

初始状态：
Initial state:

下标 / Index: 0 1 2 3 4 5 6 7 8
dp:           T F F F F F F F F

当 end = 4 时，s.slice(0, 4) = "leet" 在字典中，并且 dp[0] = true，所以 dp[4] = true。
At end = 4, s.slice(0, 4) = "leet" is in the dictionary and dp[0] is true, so dp[4] = true.
当 end = 8 时，s.slice(4, 8) = "code" 在字典中，并且 dp[4] = true，所以 dp[8] = true。
At end = 8, s.slice(4, 8) = "code" is in the dictionary and dp[4] is true, so dp[8] = true.

下标 / Index: 0 1 2 3 4 5 6 7 8
dp:           T F F F T F F F T

最终 dp[8] = true，因此 "leetcode" 可以被完整拆分。
The final state dp[8] is true, so "leetcode" can be fully segmented.

为什么不能使用贪心？ / Why Does Greedy Fail?

每次选择最长或最短的匹配单词都不能保证成功，因为当前看似合理的选择可能让后面的字符串无法拆分。
Always choosing the longest or shortest matching word does not guarantee success because a locally valid choice may leave an impossible suffix.

例如：
For example:

s = "cars"
wordDict = ["car", "ca", "rs"]

如果贪心选择较长的 "car"，剩下的 "s" 无法拆分；但正确方案是 "ca" + "rs"。
Greedily choosing the longer "car" leaves "s", which cannot be segmented, while "ca" + "rs" is valid.

动态规划会保留所有能够成功拆分的前缀状态，不会被某一次局部选择限制。
Dynamic programming preserves every reachable prefix state and is not restricted by one local choice.

复杂度 / Complexity

设：
Let:

n = s.length
L 为字典中最长单词的长度。
L be the maximum dictionary-word length.

每个结束位置最多检查 L 个起点。若把 JavaScript 的 slice() 和字符串哈希成本计入，每次子字符串处理最多需要 O(L)：
Each ending position checks at most L starting positions. Including JavaScript substring creation and hashing, each substring operation may cost up to O(L):

时间复杂度 / Time: O(n × L²)；若把子字符串查询视为 O(1)，则常简写为 O(n × L)。
O(n × L²) including substring work; it is often written as O(n × L) if substring lookup is treated as O(1).
空间复杂度 / Space: O(n + D)，其中 D 是字典内容占用的空间。
O(n + D), where D is the storage used by the dictionary.

由于本题 L <= 20，最长单词剪枝非常有效。
Since L <= 20, maximum-word-length pruning is highly effective here.

易错点 / Common Pitfalls

dp 的长度应为 s.length + 1，并设置 dp[0] = true。
Allocate s.length + 1 states and set dp[0] = true.
dp[i] 表示前 i 个字符，使用的是左闭右开区间 s.slice(start, end)。
dp[i] represents the first i characters, using the half-open range s.slice(start, end).
不能只判断子字符串是否在字典中，还必须保证 dp[start] === true。
A substring match is valid only when dp[start] === true.
同一个字典单词可以重复使用，不需要从 Set 中删除已经匹配的单词。
Dictionary words may be reused, so do not remove matched words from the Set.
题目只要求判断是否能拆分，不需要构造具体的拆分结果。
The task only asks whether segmentation is possible, not for the actual segmentation.

Word Break