## 题目地址(139. 单词拆分)

https://leetcode-cn.com/problems/word-break/

## 题目描述

```
给定一个非空字符串 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

```

## 前置知识

- [动态规划](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md)

## 公司

- 阿里
- 腾讯
- 百度
- 字节

## 思路

这道题是给定一个字典和一个句子，判断该句子是否可以由字典里面的单词组出来，一个单词可以用多次。

暴力的方法是无解的，复杂度极其高。 我们考虑其是否可以拆分为小问题来解决。
对于问题`(s, wordDict)` 我们是否可以用(s', wordDict) 来解决。 其中 s' 是 s 的子序列，
当 s'变成寻常(长度为 0)的时候问题就解决了。 我们状态转移方程变成了这道题的难点。

我们可以建立一个数组 dp, dp[i]代表 字符串 s.substring(0, i) 能否由字典里面的单词组成，经过这样的抽象我们就可以建立 dp[i - word.length] 和 dp[i] 的关系。它们有什么关系？又该如何转移呢？

我们用图来感受一下：

![139.word-break-1](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu370c2hj30n60cnmy6.jpg)

没有明白也没有关系，我们分步骤解读一下：

（以下的图左边都代表 s，右边都是 dict，灰色代表没有处理的字符，绿色代表匹配成功，红色代表匹配失败）

![139.word-break-2](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu37ydiwj30aw0b1mxc.jpg)

![139.word-break-3](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu3f3l6kj30bt0akdg0.jpg)

![139.word-break-4](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu3mmjmtj30mw09ymxp.jpg)

![139.word-break-5](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu3qr7ppj30n90kqabg.jpg)

上面分步解释了算法的基本过程，下面我们感性认识下这道题，我把它比喻为
你正在`往一个老式手电筒🔦中装电池`

![139.word-break-6](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu3rqvffj30mz0frwg3.jpg)

## 代码

代码支持： JS，CPP

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<string>& dict) {
        unordered_set<string> st(begin(dict), end(dict));
        int N = s.size();
        vector<bool> 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];
    }
};

```

**复杂度分析**

令 S 和 W 分别为字符串和字典的长度。

- 时间复杂度：$O(S ^ 3)$
- 空间复杂度：$O(S + W)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
