139. Word Break

題目網址：https://leetcode.cn/problems/word-break/

題意：給一 string s 和一 string list wordDict, 若 wordDict 中的單字能組出 s 則返回 true。

注意：wordDict 中的 string 互不相同, 且 s.length ≤ 300

Solution 1：

想法：利用 DP, 其中 dp[i] 代表 s[0~(i-1)] 是否能被拆分成若干個出現在 wordDict 中的單字, 我們要枚舉 s[0~(i-1)] 中的切割點 j, 使得 s[0~(j-1)] 和 s[j~(i-1)] 皆在 wordDict 中, 由於 j < i, 所以要計算 dp[i] 時可透過先前計算過的 d[j] 知道 s[0~j] 是否能被拆分, 然後再判斷 s[j~(i-1)] 是否在 wordDict 中即可, 故得到以下公式：

• dp[i] = dp[j] && check(s[j~(i-1)])
• check(s[j~(i-1)]) 代表檢查 s[j~(i-1)] 是否在 wordDict 中

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        const int n = s.size();
        vector<bool> dp(n + 1, false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0] = true; // 空字串一定在 wordDict 中

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};

• time：$O(n^2)$ ➔ for loop
• space：$O(n)$ ➔ dp

Solution 2：（TLE 無法通過）

想法：利用 DFS + Trie

class TrieNode{
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie{
public:
    TrieNode *root;

    Trie() : root(new TrieNode()) {}

    void insert(const string& word){
        TrieNode *node = root;
        for (const auto& ch : word) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                node->children[i] = new TrieNode();
            }
            node = node->children[i];
        }
        node->isEnd = true;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        for (const auto& word : wordDict) {
            trie.insert(word);
        }
        return dfs(s, 0);
    }

private:
    Trie trie;

    bool dfs(const string& s, const int cur){
        if (cur == s.size()) {
            return true;
        }

        TrieNode *node = trie.root;
        for (int i = cur; i < s.size(); ++i) {
            const int idx = s[i] - 'a';
            if (node->children[idx]) {
                node = node->children[idx];

                // s[cur~i] 為 word, 則以 i + 1 為開頭繼續遞迴拆分
                if (node->isEnd && dfs(s, i + 1)) {
                    return true;
                }
            } else {
                break;
            }
        }
        return false;
    }
};

• time：$O(\sum _{i=0}^{m-1}{w}_i+2^n)$, 其中 $m$ 為 wordDict 中單字的個數, $w_i$ 為 wordDict[i] 的長度, $n$ 為 s 的長度

  • $O(\sum _{i=0}^{m-1}{w}_i)$：將 wordDict 中每個單字 insert 到 trie 中

  • $O(2^n)$：判斷長度為 n 的 s 能否拆分成其他單字。$T(n)=T(n-1)+T(n-2)+\dots +T(1)$

    

• space：$O(\sum _{i=0}^{m-1}{w}_i)$ ➔ $O(26\cdot \sum _{i=0}^{m-1}{w}_i)$, worse case：trie 中所有單字都沒有重複的 prefix

Solution 3：

想法：利用 DFS + Trie + DP, 改進 Solution 2, 若 s 中 idx = cur 為開頭往後的 substring 無法由若干個 wordDict[i] 所組成, 則透過 memo 紀錄起來, 藉此來進行 pruning, 避免重複走失敗的道路

class TrieNode{
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false;
};

class Trie{
public:
    TrieNode *root;

    Trie() : root(new TrieNode()) {}

    void insert(const string& word){
        TrieNode *node = root;
        for (const auto& ch : word) {
            const int i = ch - 'a';
            if (!node->children[i]) {
                node->children[i] = new TrieNode();
            }
            node = node->children[i];
        }
        node->isEnd = true;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        for (const auto& word : wordDict) {
            trie.insert(word);
        }
        return dfs(s, 0);
    }

private:
    Trie trie;
    bool memo[300] = {false}; // 紀錄 s 中以 idx 為開頭是否能分割出 word, true 代表不行

    bool dfs(const string& s, const int cur){
        if (cur == s.size()) {
            return true;
        }

        // 若已經被標記為失敗, 則直接返回
        if (memo[cur] == true) {
            return false;
        }

        TrieNode *node = trie.root;
        for (int i = cur; i < s.size(); ++i) {
            const int idx = s[i] - 'a';
            if (node->children[idx]) {
                node = node->children[idx];
                if (node->isEnd && dfs(s, i + 1)) {
                    return true;
                }
            } else {
                break;
            }
        }

        memo[cur] = true; // 標記為失敗

        return false;
    }
};

• time：$O(\sum _{i=0}^{m-1}{w}_i+n^2)$, 其中 $m$ 為 wordDict 中單字的個數, $w_i$ 為 wordDict[i] 的長度, $n$ 為 s 的長度
  • $O(\sum _{i=0}^{m-1}{w}_i)$：將 wordDict 中每個單字 insert 到 trie 中
  • $O(n^2)$：判斷長度為 n 的 s 能否拆分成其他單字
    • $O(n^2)$ : $T(n)=T(n-1)+O(n)$, 因為有用 memo 記憶, 所以呼叫 $T(n-1)$ 即可, 因為 $T(n-1)$ 會再往下呼叫 $T(n-2)$, 依此類推 …, 每個 $T(n-i)$ 只要呼叫一次即可（因為會記住結果）。
    • $O(n)$ 是因為呼叫一次 $T(n-1)$ 後, 剩下 $T(n-2),\dots ,T(1)$ 都會計算出來。原本 $O(n)$ 應寫作 $T(n-2)+T(n-3)+\dots +T(1)$, 但是除了 $T(n-1)$, 剩下的 $T(n-i)$ 都只需 $O(1)$, 故 $T(n-2)+T(n-3)+\dots +T(1)$ 可直接寫成 $O(n)$。
• space：$O(\sum _{i=0}^{m-1}{w}_i)$ ➔ $O(26\cdot \sum _{i=0}^{m-1}{w}_i)$ + $O(1)$
  • $O(26\cdot \sum _{i=0}^{m-1}{w}_i)$：worse case：trie 中所有單字都沒有重複的 prefix
  • $O(1)$：memo 為常數空間