LeetCode - Word Break（單詞拆分）

題目描述

給定一個字符串 s 和一個字符串數組 wordDict，判斷是否可以將字符串 s 拆分為一個或多個在 wordDict 中的單詞。

範例：

輸入：s = "leetcode", wordDict = ["leet", "code"]
輸出：true
解釋：返回 true，因為 "leetcode" 可以拆分為 "leet" 和 "code"。

輸入：s = "applepenapple", wordDict = ["apple", "pen"]
輸出：true
解釋：返回 true，因為 "applepenapple" 可以拆分為 "apple", "pen" 和 "apple"。

輸入：s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出：false

限制：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 只包含小寫英文字母。

解法思路

這道題目可以使用動態規劃來解決。定義一個布爾數組 dp，其中 dp[i] 表示字符串 s 的前 i 個字符是否可以被拆分成 wordDict 中的單詞。

動態規劃步驟

1. 初始化：創建一個長度為 n + 1 的布爾數組 dp，其中 n 是字符串 s 的長度。設置 dp[0] = True，因為空字符串可以被拆分。
2. 遞推公式：對於每一個位置 i（從 1 到 n），檢查所有可能的前綴 s[0:j]，其中 j 取值範圍從 0 到 i-1，若 dp[j] 為 True 且 s[j:i] 在 wordDict 中，則 dp[i] 也應為 True。
3. 結果：返回 dp[n] 的值，即 s 是否可以完全拆分。

代碼實現

以下是 Python 的實現：

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # 空字符串可以拆分

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break  # 找到可以拆分的情況，提前退出

    return dp[n]

代碼解析

1. 初始化 word_set：將 wordDict 轉換為集合以提高查找速度。
2. 初始化 dp 數組：設置 dp 數組的大小為 n + 1，並將 dp[0] 設為 True。
3. 更新 dp：使用兩層循環，對於每個 i，檢查所有的前綴 s[j:i] 是否在 word_set 中，若是，則更新 dp[i] 為 True。
4. 返回結果：返回 dp[n]，表示字符串 s 是否可以被拆分。

時間和空間複雜度

• 時間複雜度：O(n^2)，外層循環遍歷字符串 s，內層循環檢查所有可能的前綴。
• 空間複雜度：O(n)，使用了 dp 數組來儲存每一步的結果。

優化

此解法的時間複雜度是 O(n^2)，若 wordDict 中的單詞數量較大，可以考慮使用Trie樹或其他數據結構進行優化查找，但基本動態規劃解法在許多情況下已經足夠高效。