題目
#

題目簡述
#

給一個字串 s 和一個字串字典 wordDict，判斷 s 是否可以被空格分割成一個或多個字典中單詞的序列。
注意：字典中的單詞可以重複使用，且分割後的單詞之間必須用空格分隔。

範例
#

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: 返回 true，因為 "leetcode" 可以被分割為 "leet code"。

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: 返回 true，因為 "applepenapple" 可以被分割為 "apple pen apple"。

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: 返回 false，因為 "catsandog" 無法被分割為字典中單詞的序列。雖然可以分割為 "cats and dog"，但 "and" 不在字典中。

解題思路
#

這題要求我們判斷一個字串是否可以被分割成字典中單詞的序列。我們可以使用動態規劃（Dynamic Programming）來解決這個問題，通過建立一個布林陣列來記錄每個位置是否可以被分割。

解法
#

創建一個布林陣列 dp，其中 dp[i] 表示字串前 i 個字符是否可以被分割
將字典轉換為 HashSet，方便 O(1) 查找
初始化 dp[0] = true（空字串可以被分割）
對於每個位置 i，檢查所有可能的分割點 j
如果 dp[j] 為 true 且 s.substring(j, i) 在字典中，則 dp[i] = true
返回 dp[s.length()]

步驟
#

初始化：
- 創建布林陣列 dp，長度為 s.length() + 1
- 將字典轉換為 HashSet
- 設定 dp[0] = true（基礎情況）
動態規劃：
- 遍歷字串的每個位置 i
- 對於每個位置，檢查所有可能的分割點 j
- 如果前 j 個字符可以被分割且 j 到 i 的子字串在字典中，則 dp[i] = true
返回結果：
- 返回 dp[s.length()]

例子說明
#

s = "leetcode", wordDict = ["leet","code"]

步驟	位置 i	檢查分割點 j	子字串	是否在字典中	dp[i]
初始化	0	-	-	-	`true`
第 1 步	1	0	“l”	否	`false`
第 2 步	2	0,1	“le”,“e”	否	`false`
第 3 步	3	0,1,2	“lee”,“ee”,“e”	否	`false`
第 4 步	4	0,1,2,3	“leet”,“eet”,“et”,“t”	“leet” 在字典中	`true`
第 5 步	5	0,1,2,3,4	“leetc”,“eetc”,“etc”,“tc”,“c”	否	`false`
第 6 步	6	0,1,2,3,4,5	“leetco”,“eetco”,“etco”,“tco”,“co”,“o”	否	`false`
第 7 步	7	0,1,2,3,4,5,6	“leetcod”,“eetcod”,“etcod”,“tcod”,“cod”,“od”,“d”	否	`false`
第 8 步	8	0,1,2,3,4,5,6,7	“leetcode”,“eetcode”,“etcode”,“tcode”,“code”,“ode”,“de”,“e”	“code” 在字典中	`true`

最終結果： true

分割過程說明：

位置 4：dp[4] = true，因為 “leet” 在字典中
位置 8：dp[8] = true，因為 dp[4] = true 且 “code” 在字典中
最終分割："leet" + " " + "code" = "leet code"

完整程式碼
#

java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 創建布林陣列，dp[i] 表示字串前 i 個字符是否可以被分割
        boolean[] dp = new boolean[s.length() + 1];
        // 將字典轉換為 HashSet，方便 O(1) 查找
        Set<String> set = new HashSet<>(wordDict);

        // 基礎情況：空字串可以被分割
        dp[0] = true;

        // 遍歷字串的每個位置
        for (int i = 1; i <= s.length(); i++) {
            // 檢查所有可能的分割點
            for (int j = 0; j < i; j++) {
                // 如果前 j 個字符可以被分割，且 j 到 i 的子字串在字典中
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 找到一個分割點即可，不需要繼續檢查
                }
            }
        }
        
        // 返回整個字串是否可以被分割
        return dp[s.length()];
    }
}

時間複雜度
#

時間複雜度：O(n² * m)，其中 n 是字串長度，m 是字典中最長單詞的長度
- 需要遍歷字串的每個位置：O(n)
- 對於每個位置，需要檢查所有可能的分割點：O(n)
- 每次檢查子字串是否在字典中：O(m)
空間複雜度：O(n + k)，其中 n 是字串長度，k 是字典中單詞的總長度
- 需要儲存 dp 陣列：O(n)
- 需要儲存 HashSet：O(k)