LeetCode 🔴 140. Word Break II

🔗 🔴 140. Word Break II

tags: 動態規劃(Dynamic Programming) 記憶化搜索(Memoization) 回溯(Backtracking) 剪枝(Pruning) 字典樹(Trie) 子集型回溯 位運算(Bit Manipulation) 狀態壓縮 雜湊表(Hash Table)

題意

給定一個字串 $s$ 和一個字串陣列 $wordDict$，在字串 $s$ 中加入空格來構建一個句子，使得句子中所有的單字都在 $wordDict$ 中。以 任意順序 返回所有這樣的可能句子。

注意，句子中可能會包含多個相同的單字 。

限制

• $1 \leq s.length \leq 20$
• $1 \leq wordDict.length \leq 1000$
• $1 \leq wordDict[i].length \leq 10$
• $s$ 和 $wordDict[i]$ 皆由小寫英文字母組成

思路

方法一：動態規劃(Dynamic Programming) + 記憶化搜索(Memoization) + 雜湊表(Hash Table)

類似於 139. Word Break 的動態規劃解法，同樣可以利用劃分型DP來解決，但在本題中需要返回所有可能的劃分結果。

因此令 $dp[i]$ 表示 $s[i:]$ 的所有可能劃分，則可以枚舉第一個單字的終點 $j$ ，若 $s[i:j+1]$ 在 $wordDict$ 中，則 $s[i:j+1]$ 可以作為劃分的第一個單字，而 $s[j+1:]$ 的所有可能劃分即為 $dp[j+1]$，因此 $s[i:]$ 的所有可能劃分即為 $s[i:j+1]$ 和 $dp[j+1]$ 的所有可能劃分的組合。

而在計算過程中會出現許多相同的子問題，因此可以使用 記憶化搜索(Memoization) 來避免重複計算，在 Python 中使用 @cache 裝飾器即可。

此外，由於 Python 中可以使用 join() 方法將列表轉換為字串，因此 Python 的範例程式碼中，是先保存所有可能劃分的單字列表，最後再使用 join() 方法將其轉換為字串；在 C++ 的範例程式碼中則是直接將所有可能劃分的單字串接起來。

為了更快檢查 $word$ 是否在 $wordDict$ 中，可以先將陣列 $wordDict$ 轉換為集合 $wordSet$。

複雜度分析

• 時間複雜度 $O(n \cdot 2^n)$，由於需要將子問題的結果添加到結果中，因此時間複雜度為 $O(n \cdot 2^n)$
• 空間複雜度 $O(n \cdot 2^n)$。
  • 最差情況下任何一個點都可以劃分，因此共有 $2^{n-1}$ 種劃分方式，每種劃分方式的長度為 $O(n)$，因此空間複雜度為 $O(n \cdot 2^n)$ 。
  • 就算答案所使用的空間可以被忽略，但因為使用了記憶化搜索，計算過程中的空間複雜度仍然為 $O(n \cdot 2^n)$

PythonC++

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        wordSet = set(wordDict)
        @cache # Memoization
        def dfs(i: int) -> List[List[str]]: # 返回 s[i:] 的所有可能劃分
            if i == n:
                return [[]]
            res = []
            for j in range(i, n): # 枚舉當前單字的結尾位置
                if s[i:j+1] in wordSet:
                    for words in dfs(j + 1):
                        res.append([s[i:j + 1]] + words)
            return res
        return [' '.join(words) for words in dfs(0)] # 將劃分的結果轉為字串

class Solution {
public:
    int n;
    unordered_map<int, vector<string>> memo; // Memoization
    unordered_set<string> wordSet;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        for (string& word : wordDict) wordSet.insert(word);
        return dfs(0, s);
    }
    vector<string> dfs(int i, string &s) { // 返回 s[i:] 的所有可能劃分
        if (i == n) return {""};
        if (memo.count(i)) return memo[i];
        vector<string> res;
        for (int j = i; j < n; j++) { // 枚舉當前單字的結尾位置
            string word = s.substr(i, j - i + 1);
            if (wordSet.count(word)) { 
                vector<string> sentences = dfs(j + 1, s);
                for (string& st : sentences) {
                    res.push_back(word + (st.empty() ? "" : " ") + st);
                }
            }
        }
        return memo[i] = res;
    }
};

方法二：回溯(Backtracking) + 字典樹(Trie)

在方法一中，需要枚舉所有的終點 $j$ ，才能檢查 $word = s[i:j+1]$ 是否在 $wordDict$ 中，那有沒有一個辦法可以在檢查到 $j$ 時，就可以確定 $j+1$ 也不會是劃分的終點呢？

為了達到這個目的，可以使用 字典樹(Trie) 來保存 $wordDict$ 中的所有單字，這樣在檢查 $s[i:j+1]$ 是否在 $wordDict$ 中時，只需要在 Trie 中查找即可。

• 若 $s[i:j+1]$ 代表的節點不在 Trie 中，則 $s[i:j+2]$ 一定不會在 $wordDict$ 中。
• 若 $s[i:j+1]$ 代表的節點在 Trie 中，則可以繼續往下找，並且若該節點是單字的結尾 ($isEnd = True$)，則可以進行劃分。

因此，我們可以寫出一個回溯函數 $dfs(i, cur, word)$，其中 $i$ 表示當前檢查的位置，$cur$ 表示 Trie 中當前的節點，$word$ 表示當前的單字。

• 首先定義終止條件，若 $i == n$，則表示已經檢查完所有字元，此時若 $cur$ 等於 Trie 的根節點，則表示最後一個單字也在 Trie 中，可以將劃分的結果添加到答案中。
• 然後檢查 $word + s[i]$ 是否在 Trie 中，由於傳入了 $cur$ 節點，因此檢查 $s[i]$ 是否在 $cur.children$ 中即可。

  • 若 $s[i]$ 不在 Trie 中，則直接返回，即 剪枝(Pruning) 。

  • 若 $s[i]$ 在 Trie 中，則可以將 $cur$ 更新為 $nxt = cur.children[s[i]-\text{'a'}]$，繼續往下找，即不劃分；

  • 若 $s[i]$ 在 Trie 中，且 $nxt$ 是單字的結尾，則可以進行劃分，將 $word$ 添加到路徑 $path$ 中。此時需要將 $cur$ 重置為 Trie 的根節點，$word$ 重置為空字串，從頭開始找。

同方法一，由於 C++ 不像 Python 有 join() 方法，因此在 C++ 的範例程式碼中，是直接將所有可能劃分的單字串接起來。在恢復狀態時， Python 是使用 path.pop() 來恢復狀態；而 C++ 的寫法中是直接將 $path$ 作為參數傳遞，這樣在遞迴時就不需要恢復狀態。但我個人認為 Python 的寫法更加直觀，可以用 Python 的寫法來理解。

複雜度分析

• 時間複雜度 $O(S + n \cdot 2^n)$，其中 $S$ 為 $wordDict$ 中所有單字的總長度，$n$ 為 $s$ 的長度。可以視為有 $O(2^n)$ 個遞迴終點，每個遞迴終點需要 $O(n)$ 的時間將劃分的結果串接起來並添加到答案中。
• 空間複雜度 $O(S + n)$，不計算答案的空間。空間複雜度主要取決於 Trie 的空間複雜度 $O(S)$ 、遞迴調用的深度 $O(n)$、路徑 $path$ 的空間複雜度 $O(n)$。

PythonC++

class Node: # Trie Node
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        root = Node() # Trie
        for word in wordDict:
            cur = root
            for ch in word:
                idx = ord(ch) - ord('a')
                if cur.children[idx] is None:
                    cur.children[idx] = Node()
                cur = cur.children[idx]
            cur.isEnd = True # 標記當前 Trie 節點是某個單字的結尾
        ans = []
        path = []
        def dfs(i: int, cur: Node, word: str) -> None: # Backtracking
            if i == n:
                if cur == root:
                    ans.append(" ".join(path))
                return
            idx = ord(s[i]) - ord('a')
            if cur.children[idx] is None: # 如果當前字元不在 Trie 中，則直接返回 (剪枝)
                return
            word += s[i] # 當前字元加入 word
            nxt = cur.children[idx]
            dfs(i + 1, nxt, word) # 不劃分，繼續往下找
            if nxt.isEnd: # 當前字元是單字的結尾，可以劃分
                path.append(word)
                dfs(i + 1, root, "") # 劃分，繼續從 Trie 的根節點開始
                path.pop()
        dfs(0, root, "")
        return ans

class Node { // Trie Node
public:
    vector<Node*> children;
    bool isEnd;
    Node() : children(26), isEnd(false) {}
};
class Solution {
public:
    int n;
    string s;
    Node* root = new Node(); // Trie
    vector<string> ans;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        this->s = s;
        for (string& word : wordDict) {
            Node* cur = root;
            for (char ch : word) {
                int idx = ch - 'a';
                if (cur->children[idx] == nullptr) {
                    cur->children[idx] = new Node();
                }
                cur = cur->children[idx];
            }
            cur->isEnd = true; // 標記當前 Trie 節點是某個單字的結尾
        }
        dfs(0, root, "", "");
        return ans;
    }
    void dfs(int i, Node* cur, string word, string path) { // Backtracking
        if (i == n) {
            if (cur == root) ans.push_back(path);
            return;
        }
        if (!cur->children[s[i]-'a']) return; // 如果當前字元不在 Trie 中，則直接返回 (剪枝)
        word += s[i]; // 當前字元加入 word
        Node* nxt = cur->children[s[i]-'a'];
        dfs(i + 1, nxt, word, path); // 不劃分，繼續往下找
        if (nxt->isEnd) { // 當前字元是單字的結尾，可以劃分
            path += (path.empty() ? "" : " ") + word;
            dfs(i + 1, root, "", path); // 劃分，繼續從 Trie 的根節點開始
        }
    }
};

方法三：狀態壓縮，枚舉劃分點

上面兩種方式都是在需要劃分時進行遞迴，那不妨嘗試直接枚舉所有可能的劃分點，這樣就不需要進行遞迴，可以直接得到答案。而長度為 $n$ 的字串 $s$，可以劃分的劃分點有 $n-1$ 個，因此可以使用狀態壓縮的方式枚舉所有可能的劃分點，即枚舉所有 $2^{n-1}$ 個子集。

對於每個子集 $i$，若 $i$ 的第 $j$ 個位為 $1$，則表示在 $s[j]$ 後需要進行劃分：

• Python 的寫法中是將所有 $s[j]$ 都先添加到 $word$ 中，在需要劃分時檢查 $word$ 是否在 $wordDict$ 中，若在則可以添加到 $path$ 中，並重置 $word$ 為空字串；否則則代表這個劃分是無效的，直接跳過。
• C++ 的寫法中是只使用一個字串 $res$ ，並且持續將 $s[j]$ 添加到 $res$ 中，使用 $k$ 來保存上個劃分在 $res$ 中的位置。在檢查是否為有效劃分時，是檢查 $s[k+1:]$ 是否在 $wordDict$ 中，若為有效劃分且 $j \neq n-1$ 則可以在 $res$ 後添加空格。

同樣地，為了更快檢查 $word$ 是否在 $wordDict$ 中，可以先將陣列 $wordDict$ 轉換為集合 $wordSet$。

複雜度分析

• 時間複雜度 $O(n \cdot 2^n)$，枚舉所有 $2^{n-1}$ 個子集，每個子集需要 $O(n)$ 的時間。
• 空間複雜度 $O(n)$，每次枚舉子集時需要 $O(n)$ 的空間來保存劃分的結果。

PythonC++

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        wordSet = set(wordDict)
        ans = []
        for i in range(0, 1 << (n - 1)): # 枚舉所有劃分點形成的子集合
            path = [] # 劃分結果
            word = "" # 當前單字
            for j in range(n):
                word += s[j]
                if i & (1 << j) or j == n - 1: # 在 s[j] 之後要劃分
                    if word not in wordSet: # 無法劃分
                        break
                    path.append(word)
                    word = ""
            else:
                ans.append(" ".join(path))
        return ans

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<string> ans;
        for (int i = 0; i < (1 << (n - 1)); i++) {
            string res = "";
            int k = -1;
            bool valid = true;
            for (int j = 0; j < n && valid; j++) {
                res += s[j];
                if (i & (1 << j) || j == n - 1) {
                    if (!wordSet.count(res.substr(k + 1))){
                        valid = false;
                        break;
                    }
                    if (j != n - 1) res += " ";
                    k = res.size() - 1;
                }
            }
            if (valid) ans.push_back(res);
        }
        return ans;
    }
};

參考資料

• 【宫水三叶】运用「二进制枚举」找具体方案

---

寫在最後

Cover photo is generated by @たろたろ, thanks for their work!

標籤很多的題目，相對應的也有很多解法。