DAY 9 試題

問題描述

給定一個字串 s 和一個字典 wordDict，其中字典包含多個單詞。請判斷字串 s 是否能夠被分割為一組以空格分隔的字典單詞序列。可以重複使用字典中的單詞。

範例 1：

• 輸入: s = "leetcode", wordDict = ["leet", "code"]
• 輸出: true
• 解釋: 字串可以被分割成 "leet code"，這兩個單詞都在字典中。

範例 2：

• 輸入: s = "applepenapple", wordDict = ["apple", "pen"]
• 輸出: true
• 解釋: 字串可以被分割成 "apple pen apple"，同樣符合字典的單詞。

範例 3：

• 輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
• 輸出: false
• 解釋: 無法找到符合的分割方式，字典中的單詞無法完全匹配。

解題思路

這題是典型的動態規劃問題。我們可以通過設置一個布林值陣列 dp 來表示字串從開頭到某個索引位置是否能被字典中的單詞組成。

具體思路如下：

1. 設置一個長度為 s.size() + 1 的布林值陣列 dp，dp[i] 代表從字串開頭到索引 i-1 的子字串能否被字典中的單詞組成。dp[0] 初始化為 true，代表空字串可以被分割。

2. 遍歷字串 s，對於每個索引 i，再次從 0 到 i 遍歷，檢查子字串 s[j:i] 是否存在於字典 wordDict 中，且 dp[j] 是否為 true。如果滿足條件，則將 dp[i] 設為 true，表示從開頭到 i 可以被分割。

3. 最後，檢查 dp[s.size()]，如果為 true，則表示字串 s 可以完全按照字典中的單詞分割。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());  // 使用集合來儲存字典單詞
        vector<bool> dp(s.size() + 1, false);  // 動態規劃陣列，dp[i] 代表 s 的前 i 個字符是否可以被字典分割
        dp[0] = true;  // 空字串可以被分割

        // 動態規劃填表過程
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                // 檢查子字串 s[j:i] 是否存在於字典中，並且 dp[j] 為 true
                if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    dp[i] = true;
                    break;  // 一旦找到可分割的方式，立即跳出內層循環
                }
            }
        }

        return dp[s.size()];  // 返回整個字串是否可以被分割
    }
};

解法重點與分析

1. 字典處理：我們使用 unordered_set 來儲存字典中的單詞，因為集合的查找效率較高，能快速檢查某個單詞是否存在於字典中。

2. 動態規劃表：dp[i] 表示字串的前 i 個字符能否通過字典中的單詞進行分割。這樣我們可以逐步構建出對應的結果。

3. 雙層循環：外層循環遍歷字串 s 的每個字符，內層循環遍歷當前字符之前的所有子字串，並檢查該子字串是否可以由字典分割。每當找到一個符合條件的子字串，dp[i] 就被設為 true，並且立即跳出內層循環。

4. 時間複雜度：這個演算法的時間複雜度是 𝑂(𝑛^2)，其中 n 是字串的長度，內層循環的子字串檢查以及集合的查找操作也很高效。

總結

本題的核心在於如何使用動態規劃來逐步解決字串分割問題。動態規劃表 dp 記錄了每個位置之前的字串是否能夠被分割，我們透過檢查每個子字串是否存在於字典中，來決定當前字串是否能夠被分割。這樣的解法能夠有效地在合理的時間內解決這類字串分割問題。

以上是第九天的自學內容分享，謝謝大家。