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.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

解答

• 方法一

範例：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

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

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

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];
};