Word Break
给定一个字符串 s 和一个单词列表 wordDict。如果你能将 s 拆分成若干部分，且每部分都是 wordDict 中的单词，则返回 true，否则返回 false。
这些部分要保持原有顺序，并且恰好使用 s 中的每个字母一次。一个单词可以使用任意次，你不必使用所有单词。
函数
- sstring
- 要拆分成单词的字符串
- wordDictstring-array
- 你可以使用这些单词，每个单词都可以使用任意多次
- 返回值boolean
- 如果 s 可以拆分成字典中的单词，则为 true，否则为 false
约束条件
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20s，并且每个单词都只包含小写英文字母。wordDict中的单词各不相同。
示例
- 输入
- s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
- 输出
- true
- 解释
- 把它切分成
sun、flower、seed。在sun后面取flow会剩下er，没有单词以它开头，所以第一个能匹配的单词不一定总是正确的。
- 输入
- s = "bananaban"wordDict = ["ban", "ana"]
- 输出
- true
- 解释
ban+ana+ban覆盖了整个字符串，并且使用了两次ban，这是允许的。
- 输入
- s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
- 输出
- false
- 解释
pine+apple和pineapple都会留下tart。只有tar能放在那里，这样会剩下一个孤零零的t，所以没有一种切法可行。
进阶
返回有效切分所需的最少单词数；如果无法切分 s，则返回 -1。表格中有什么变化？运行时间会改变吗？
提示
逐个打开提示，每个都会多透露一点。
每次切分时，第一个部分是一个以
s开头的单词。选好它之后，还剩下什么问题？是否可以从某个索引开始剪掉直到末尾的字母，只取决于该索引。这样的问题只有
n + 1个，所以记住每个问题的答案，尤其是那些答案为false的。令
canEnd[i]表示前i个字母能否切分，并令canEnd[0] = true。当某个canEnd[start]为 true，且从start到end的字母组成一个单词时，canEnd[end]就为 true。将单词存入哈希集合，并且只尝试长度不超过最长单词的片段。
题解
一次只处理一个单词行不通，而尝试每种切分方式的时间复杂度是指数级的。但剩余的 s 能否切分，只取决于它从哪里开始，因此只有 n + 1 个问题。下面，n 是 s 的长度，m 是单词数，L 是最长单词的长度。
尝试每个单词在每个位置的情况
结果正确，但无法在最大的测试中运行完毕
思路
第一段必须是一个以 s 开头的单词。尝试每个这样的单词，并对剩下的字母提出同样的问题；剩余部分为空，就表示所有字母都已切分。依次尝试每个首词，再尝试每个第二个词，不会漏掉有效的切分。
它会反复检查相同的剩余部分。假设有 299 个 a，后面跟着一个 b，单词包括 a、aa，一直到由十个 a 组成的单词，那么把这些 a 切分成若干块并到达 b 后失败的方式超过 10^89 种，而递归会把它们全部尝试一遍。
算法
- 编写
canSplit(start)：从start到末尾的字母能否拆分？如果start等于s的长度，返回true。 - 对于
s中从索引start开始的每个单词，如果canSplit(start + its length)为true，则返回true。 - 否则返回
false。答案是canSplit(0)。
def wordBreak(s, wordDict):
def can_split(start):
# Can s[start:] be cut into dictionary words?
if start == len(s):
return True # nothing left to cut
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
return True
return False
return can_split(0)使用备忘录进行递归
思路
余数的答案只取决于 start，它有 n + 1 个可能值。在由 a 组成的示例中，索引 20 处的余数可以在两个长度为十的块之后、二十个单独的 a 之后，或者通过无数其他方式到达，而且每次结果都是 false。把每个 start 的答案存储一次，然后重复使用。
备忘录必须保留 false 答案。遇到 true 会立即结束整个搜索，所以重复的工作都发生在失败的分支中。
每个 start 都会尝试每个单词，最多比较 L 个字母：时间复杂度为 O(n × m × L)，最多进行 6 × 10^6 次字母检查，空间复杂度为 O(n)。
算法
- 创建一份备忘录，每个索引对应一个槽位，并将每个槽位标记为尚未计算。
- 在
canSplit(start)中，如果到达s的末尾，就返回true；如果槽位中有已保存的答案，就返回该答案。 - 否则，像普通递归那样尝试每个单词，将结果存入槽位，包括
false，然后返回该结果。
def wordBreak(s, wordDict):
memo = [None] * len(s) # memo[start]: answer for s[start:], None until worked out
def can_split(start):
if start == len(s):
return True
if memo[start] is not None:
return memo[start]
result = False
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
result = True
break
memo[start] = result
return result
return can_split(0)使用哈希集合对前缀进行自底向上的处理
思路
处理前缀。让 canEnd[i] 表示前 i 个字母能否切分；canEnd[0] 是 true，因为空前缀不需要任何单词。当最后一段（从 start 到 end）是一个单词，且 canEnd[start] 是 true 时，前 end 个字母就能切分。从左到右填充时，你需要的每个 canEnd[start] 都已经确定。
把单词放进哈希集合。没有单词的长度超过 L，所以无论字典多大，在 end 处结束的片段中，只有 L 个可能匹配。对于 sunflowerseed，canEnd 在 0、3、7、9 和 13 处为 true；7 处的死路不会造成影响。
n 个位置中的每个位置最多查找 L 个片段，每个片段的构建和哈希计算最多需要 L 步：O(n × L²)，最多 1.2 × 10^5 步，此外集合还需要 O(m × L)。
算法
- 将单词放入哈希集合中，并记下最长单词的长度
L。 - 创建一个包含
n + 1个元素的canEnd，所有元素都设为false，并将canEnd[0]设为true。 - 对于从 1 到
n的每个end，以及从 1 到min(L, end)的每个length：如果canEnd[end-length]为true，并且以end结尾、长度为length的片段在集合中，就将canEnd[end]设为true并停止。 - 返回
canEnd[n]。
def wordBreak(s, wordDict):
words = set(wordDict)
longest = max(len(word) for word in wordDict)
n = len(s)
# can_end[i]: the first i letters split into dictionary words
can_end = [False] * (n + 1)
can_end[0] = True # the empty prefix needs no words
for end in range(1, n + 1):
# The last word is s[end-length:end], and no word is longer than longest.
for length in range(1, min(longest, end) + 1):
if can_end[end - length] and s[end - length:end] in words:
can_end[end] = True
break
return can_end[n]
易错点和边界情况
- 贪心切分。优先选择最长单词，会把
carpetal切成carpet，导致al无法处理，尽管car+petal可以成功；优先选择最短单词，则会在sunflowerseed处卡住。 - 只在备忘录中保存
true的答案。重复计算发生在false分支中，所以由 a 组成的示例仍然需要指数级的计算量。 - 表格少建了一项。
canEnd需要n + 1项，对应长度从 0 到n的前缀。 - 比较范围超出了
s的末尾，例如将单词abc与剩余部分ab比较。先检查长度。 - 在 Lua 和 R 中，字符串位置从 1 开始：以字母
e结尾、长度为k的片段，其起始位置是e-k+1。
常见问题3
Word Break 的时间复杂度是多少？
使用哈希集合的自底向上表格算法的运行时间为 O(m × L + n × L²)，其中 n 是 s 的长度，m 是单词数量，L 是最长单词的长度。在每个位置比较每个单词的开销为 O(n × m × L)。普通递归的时间复杂度是指数级的。
Word Break 是动态规划问题还是图问题？
两种都可以。作为动态规划，canEnd[i] 表示前 i 个字母能否拆分。作为图，每个索引都是一个节点，如果两个节点之间的字母能组成一个单词，就从 i 向 j 连一条边，然后判断能否从 0 到达 n。广度优先搜索完成的工作与这张表相同。
怎样列出每个句子，而不是返回 true 或 false？
回溯：在每个索引处尝试所有适合的单词，对剩余部分进行递归，并记住每个索引对应的句子列表。先运行真值或假值表，这样无法拆分的字符串就会跳过搜索。句子的数量可能呈指数级增长，因此输出大小决定了运行时间。
def wordBreak(s, wordDict):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
预期输出
true