139. 单词拆分 Medium
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
解题思路
输入： 一个字符串 s 和一个字符串列表 wordDict
输出： 判断这个字符串是否可以被字符串列表中的一个或多个单词拼接出来
本题属于线性DP问题。
可以想象你在读字符串 s，一边走一边问自己：
“走到这里的时候，前面那一段能不能被切开？”
于是我们可以用一个数组 dp 来记录：
dp[i] = True 表示 s[0:i]（前 i 个字符）可以被切开。
初始：dp[0] = True（空串当然算“能切开”）。
然后我们不断往后走：
每到 i 位置，就看看前面某个 j，如果 dp[j] 为 True， 并且 s[j:i] 在字典里，就说明 dp[i] = True。
最后看 dp[len(s)] 就知道整串能不能切开。
代码实现
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# 把 wordDict 转成集合，方便 O(1) 判断某个子串是否在字典中
wordDictSet = set(wordDict)
n = len(s)
# dp[i] 表示 s[:i]（前 i 个字符）能否被拆分成字典里的单词
dp = [False] * (n + 1)
# 空字符串可以认为是“能被拆分的”，作为递推的起点
dp[0] = True
# 外层循环：i 表示前 i 个字符
for i in range(1, n + 1):
# 内层循环：尝试所有切分点 j
# 如果 s[:j] 可以拆分，并且 s[j:i] 在字典中
# 那么 s[:i] 就可以拆分
for j in range(i):
if dp[j] and s[j:i] in wordDictSet:
dp[i] = True
break # 找到一个可行切分即可，不用继续
# 返回整个字符串是否能被拆分
return dp[n]var wordBreak = function(s, wordDict) {
// 将字典转为 Set，提高查询效率 O(1)
const wordSet = new Set(wordDict);
// dp[i] 表示 s[0..i-1] 是否可以被拆分成字典里的单词
const dp = Array(s.length + 1).fill(false);
// 空字符串可被拆分，作为递推起点
dp[0] = true;
// 外层循环：枚举子串的终点 i
for (let i = 1; i < s.length + 1; i++) {
// 内层循环：枚举切分点 j
// 如果 s[0..j-1] 可拆分，并且 s[j..i-1] 在字典里
// 那么 s[0..i-1] 就可以拆分
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true;
break; // 找到一个切分方法即可，不用继续
}
}
}
// 返回整个字符串是否能被拆分
return dp[s.length];
};复杂度分析
时间复杂度：O(n ^ 2)
空间复杂度：o(n)