单词拆分
给你一个字符串 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
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串互不相同
动态规划：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
int n = s.size();
int maxLen = 0;
for (string& word : wordDict)
{
maxLen = max(maxLen, (int)word.size());
}
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++)
{
for (int len = 1; len <= maxLen && len <= i; len++)
{
if (dp[i - len] && wordSet.count(s.substr(i - len, len)))
{
dp[i] = true;
break;
}
}
}
return dp[n];
}
};
核心思想
这题要判断字符串 s 能不能被拆成若干个字典单词。
最直接的想法是尝试所有切分方式。
比如对于字符串：
leetcode
可以试着切成：
l+eetcodele+etcodelee+tcodeleet+code
如果前半段是字典里的单词，就继续判断后半段。
但是这样会产生大量重复判断。
例如某一段后缀可能会被不同的切分路径反复检查。
所以我们把“某个前缀能不能被拆分”保存下来，用动态规划避免重复计算。
这题最关键的观察是：
如果
s[0...j - 1]可以被拆分，并且s[j...i - 1]是字典中的单词，那么s[0...i - 1]也可以被拆分。
状态定义
定义：
dp[i] 表示字符串 s 的前 i 个字符能否由字典中的单词拼接出来。
也就是判断：
s[0...i - 1]
能不能被拆分。
题目要求的答案就是：
dp[n]
其中 n = s.size()。
递推公式推导
现在考虑如何判断 dp[i]。
如果存在一个切分点 j，满足：
dp[j] == trues[j...i - 1]在字典中
那么前 j 个字符已经可以被拆分，后面这一段又刚好是一个字典单词。
所以前 i 个字符也可以被拆分：
dp[i] = true
换句话说：
s[0...i - 1] = s[0...j - 1] + s[j...i - 1]
只要左半部分可以拆分，右半部分是一个完整单词，就能得到一个合法方案。
因此递推逻辑是：
if (dp[j] && wordSet.count(s.substr(j, i - j)))
{
dp[i] = true;
}
代码里没有直接枚举 j，而是枚举最后一个单词的长度 len：
j = i - len
这样方便用 maxLen 限制枚举范围。
为什么可以用 maxLen 优化
字典中每个单词的长度最多是 20。
如果最后一个单词长度超过字典中最长单词长度，那么它一定不可能出现在字典中。
所以对每个位置 i，没有必要检查所有 j。
只需要枚举：
1 <= len <= maxLen
并且 len <= i。
这样可以减少很多无意义的字符串查找。
边界情况
dp[0] = true
它表示空字符串可以被成功拆分。
这不是说题目里真的有空单词，而是为了让递推有起点。
例如：
s = "leetcode"
wordDict = ["leet", "code"]
当检查前 4 个字符 "leet" 时：
dp[0] == true"leet"在字典中
所以可以推出：
dp[4] = true
如果没有 dp[0] = true，第一个单词就无法被正确接上。
为什么字典单词可以重复使用
题目允许字典中的单词重复使用。
在动态规划中，每次判断 dp[i] 时，只关心某一段子串是不是存在于 wordSet 中。
不会因为某个单词之前用过，就把它从字典中删除。
例如：
s = "applepenapple"
wordDict = ["apple", "pen"]
第一次使用 "apple" 可以得到 dp[5] = true。
后面再次遇到 "apple" 时，仍然可以继续使用它，最终得到 dp[13] = true。
这正好符合题意。
正确性证明
我们证明：算法返回的结果满足题意。
结论 1：如果 dp[i] == true，那么 s 的前 i 个字符一定可以由字典单词拼接出来
dp[i] 只会在下面条件成立时被设为 true：
dp[i - len] && wordSet.count(s.substr(i - len, len))
其中 dp[i - len] == true 表示前 i - len 个字符可以被拆分。
s.substr(i - len, len) 在字典中，说明最后这一段是一个合法单词。
把前面的合法拆分和最后这个单词拼起来，就得到 s 的前 i 个字符。
所以如果 dp[i] == true，它一定对应一个合法拆分。
结论 2：如果 s 的前 i 个字符可以被字典单词拼接出来，那么算法一定会令 dp[i] == true
假设 s[0...i - 1] 存在一个合法拆分。
看这个拆分中的最后一个单词，设它是：
s[j...i - 1]
那么：
s[0...j - 1]也一定可以被合法拆分s[j...i - 1]一定在字典中
根据动态规划从小到大的计算顺序，计算 dp[i] 之前，dp[j] 已经被算好。
由前半部分可以拆分可知：
dp[j] == true
当算法枚举到 len = i - j 时，会检查到最后这个单词。
于是 dp[i] 会被设置为 true。
所以算法不会漏掉任何合法拆分。
结论 3：dp[0] = true 是正确的递推起点
空字符串不需要使用任何单词就可以完成拼接。
因此 dp[0] = true 合理。
它保证当 s 的某个前缀本身就是字典单词时，可以通过：
dp[0] + 这个单词
推出对应状态为 true。
得出结论
由结论 1 可知，算法不会把不能拆分的前缀误判为可以拆分。
由结论 2 可知，算法不会漏掉任何可以拆分的前缀。
由结论 3 可知，递推起点正确。
因此 dp[n] 为 true 当且仅当整个字符串 s 可以由字典单词拼接出来，算法正确。
举例理解
以：
s = "leetcode"
wordDict = ["leet", "code"]
为例。
初始化：
dp[0] = true
然后从左到右计算：
- 检查到
"leet"时，因为dp[0] == true且"leet"在字典中，所以dp[4] = true - 继续往后检查到
"code"时，因为dp[4] == true且"code"在字典中，所以dp[8] = true
最终：
dp[8] == true
说明 "leetcode" 可以被拆分成：
"leet" + "code"
再看：
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
虽然前面可以拆出：
"cat""cats""cats" + "and""cat" + "sand"
但是最后都无法接出完整的 "og"。
所以最终 dp[n] == false。
复杂度分析
设字符串长度为 n，字典中最长单词长度为 L。
对每个位置 i，最多枚举 L 种最后单词长度。
每次需要截取长度不超过 L 的子串并在哈希表中查询。
所以时间复杂度可以写作：
O(n * L^2)
由于本题中 L <= 20，L 很小，实际运行非常高效。
哈希表中存储了字典单词，动态规划数组长度为 n + 1。
所以空间复杂度是：
`O(n + wordDict.length)