# 139. Word Break

### Leetcode

<https://leetcode.com/problems/word-break/description/>

### 題目

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "leetcode", wordDict = ["leet","code"]
</strong><strong>Output: true
</strong><strong>Explanation: Return true because "leetcode" can be segmented as "leet code".
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "applepenapple", wordDict = ["apple","pen"]
</strong><strong>Output: true
</strong><strong>Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
</strong>Note that you are allowed to reuse a dictionary word.
</code></pre>

**Example 3:**

<pre><code><strong>Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
</strong><strong>Output: false
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

範例：`s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]`

1. 先找出 `s` 字串開頭字母的 `wordDict`，`s` 第一個字母為 `c`，所以找出來的是 `["cats", "cat"]`
2. 判斷找出來的 `word` 在 `s` 中是否為開頭的字串

   ex. `"cats"` 為 `s` 中的前四個字母 => 確認是開頭的字串
3. 找出 `s` 開頭的字串後，接著往後找 `s` 剩餘的字串

   ex. `"cats"` 已經被找到了，接著要找的剩餘字串為 `"andog"`

一直重複以上三個步驟，直到最後剩餘的字串為空代表利用 `wordDict` 可以組出 `s`

另外為了防止超時，所以在過程中都需要紀錄每個字串是否找到

```javascript
var wordBreak = function (s, wordDict) {
    const map = {};

    const findWord = (s) => {
        // 最後剩餘的字串為空代表找到了 => 回傳 true
        if (s === '' || map[s]) return true;
        // 字串之前找過沒找到 => 回傳 false
        if (map[s] === false) return false;

        const char = s[0];
        const words = wordDict.filter(word => word.startsWith(char));
        if (words) {
            for (let i = 0; i < words.length; i++) {
                const word = words[i];
                // 判斷 s 開頭的字串是不是 word 
                if (s.startsWith(word)) {
                    map[word] = true;
                    // 繼續找 s 後面剩餘的字串
                    const nextWord = s.slice(word.length);
                    if (findWord(nextWord)) {
                        map[nextWord] = true;
                        return true;
                    };
                }
            }
        }

        map[s] = false;
        return false;
    }

    return findWord(s);
};
```

* **方法二 - DP**

`dp[i]` 代表到第 i 個字母前的字串，是否能夠用 `wordDict` 組成

例如： `s="apple", wordDict = ["app"]`，這時候的 `dp[2] = true`

而求出 `dp[i]` 的關鍵公式是：`dp[i] = dp[j] && wordDict.includes(word)`，`word` 代表的是從 `j` 切到 `i` 的字串

例如： `s="apple", wordDict = ["app", "le"]`

當 `i = 4` 時，`j` 從 0 遍歷到 4

* `j = 0`

`dp[0] = true` 代表的是到第 0 個字母前的字串 => `""`

`word = s.slice(0, 4)`  => `"apple"`

`dp[4] = dp[0] && wordDict.includes(word) = false`

```
apple
    ^  (i = 4)
^      (j = 0) ""
```

* `j = 1`

`dp[1] = false` 代表的是到第 1 個字母前的字串 => `"a"`

`word = s.slice(1, 4)`  => `"pple"`

`dp[4] = dp[1] && wordDict.includes(word) = false`

```
apple
    ^  (i = 4) 
 ^     (j = 1) a && pple
```

* `j = 2`

`dp[2] = false` 代表的是到第 2 個字母前的字串 => `"ap"`

`word = s.slice(2, 4)`  => `"ple"`

`dp[4] = dp[2] && wordDict.includes(word) = false`

```
apple
    ^  (i = 4) 
  ^    (j = 2) ap && ple
```

* `j = 3`

`dp[3] = true` 代表的是到第 3 個字母前的字串 => `"app"`

`word = s.slice(3, 4)`  => `"le"`

`dp[4] = dp[3] && wordDict.includes(word) = true`

```
apple
    ^  (i = 4) 
   ^   (j = 3) app && le
```

可以發現當 `j = 3` 的時候，就可以用 `app` 及 `el` 組出 `apple` 了，所以最終答案是 `true`

```javascript
var wordBreak = function (s, wordDict) {
    // 初始值：第 0 個字母為可以組出來的
    const dp = [true];

    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            // 取出後面的字串
            const word = s.slice(j, i);
            // dp[j] 及後面字串都可以拼出來 => 代表 dp[i] 也是可以組出來的
            dp[i] = dp[j] && wordDict.includes(word);
            if (dp[i]) {
                break;
            }
        }
    }

    return dp[s.length];
};
```
