# 0139. 单词拆分
### 题目地址(139. 单词拆分)
### 题目描述
```
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 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
```
### 前置知识
* [动态规划](/leetcode-solution/thinkings/dynamic-programming.md)
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
这道题是给定一个字典和一个句子，判断该句子是否可以由字典里面的单词组出来，一个单词可以用多次。
暴力的方法是无解的，复杂度比较高，但是可以通过。
暴力思路是从匹配位置 0 开始匹配， 在 wordDict 中一个个找，如果其能和 s 匹配上就尝试进行匹配，并更新匹配位置。
比如 s = "leetcode", wordDict = \["leet", "code"]。
那么：
* 先试试 leet 可以匹配么？可以的，匹配后 s 剩下 code，继续在 wordDict 中找。
* leet 可以匹配么？不能！code 能够匹配么？可以！返回 true 结束
如果 wordDict 遍历一次没有任何进展，那么直接返回 false。
注意到如果匹配成功一次后，本质是把问题规模缩小了，问题性质不变，因此可以使用动态规划来解决。
```py
@cache
def dp(pos):
if pos == len(s): return True
for word in wordDict:
if s[pos:pos+len(word)] == word and dp(pos + len(word)): return True
return False
return dp(0)
```
复杂度为 $O(n^2 \* m)$ 其中 n 为 s 长度， m 为 wordDict 长度。
我们用图来感受一下：
接下来我们以题目给的例子分步骤解读一下：
（以下的图左边都代表 s，右边都是 dict，灰色代表没有处理的字符，绿色代表匹配成功，红色代表匹配失败）
上面分步解释了算法的基本过程，下面我们感性认识下这道题，我把它比喻为 你正在`往一个老式手电筒🔦中装电池`
我们可以进一步优化， 使得复杂度和 m 无关。优化的关键是在 dp 函数内部枚举匹配的长度 k。这样我们截取 s\[pos:pos+k] 其中 pos 表示当前匹配到的位置。然后只要看 s\[pos:pos+k] 在 wordDict 存在与否就行。存在了就更新匹配位置继续，不存在就继续。而*看 s\[pos:pos+k] 在 wordDict 存在与否就行* 是可以通过将 wordDict 中放入哈希集合中进行优化的，时间复杂度 O(1)，牺牲一点空间，空间复杂度 O(m)
### 代码
代码支持： Python3, JS，CPP
Python3 Code:
```py
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict = set(wordDict)
@cache
def dp(pos):
if pos == len(s): return True
cur = ''
for nxt in range(pos, len(s)):
cur += s[nxt]
if cur in wordDict and dp(nxt + 1): return True
return False
return dp(0)
```
JS Code:
```js
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const dp = Array(s.length + 1);
dp[0] = true;
for (let i = 0; i < s.length + 1; i++) {
for (let word of wordDict) {
if (word.length <= i && dp[i - word.length]) {
if (s.substring(i - word.length, i) === word) {
dp[i] = true;
}
}
}
}
return dp[s.length] || false;
};
```
CPP Code:
```cpp
class Solution {
public:
bool wordBreak(string s, vector& dict) {
unordered_set st(begin(dict), end(dict));
int N = s.size();
vector dp(N + 1);
dp[0] = true;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i && !dp[i]; ++j) {
dp[i] = dp[j] && st.count(s.substr(j, i - j));
}
}
return dp[N];
}
};
```
**复杂度分析**
令 n 和 m 分别为字符串和字典的长度。
* 时间复杂度：$O(n ^ 2)$
* 空间复杂度：$O(m)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/139.word-break.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.