力扣139.單詞拆分

本題要求判斷給定的字符串 s 是否可以被空格拆分為一個或多個在字典 wordDict 中出現的單詞，且不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用，這是一個典型的動態規劃問題。

動態規劃思路

1. 定義狀態：
   • 定義一個布爾類型的數組 dp，其中 dp[i] 表示字符串 s 的前 i 個字符能否被拆分成 wordDict 中的單詞。數組長度為 s.length + 1，因為要考慮到空字符串的情況。
   • 初始化 dp[0] = true，表示空字符串可以被拆分，這是動態規劃的初始條件。
2. 狀態轉移方程：
   • 對于每個位置 i（從 1 到 s.length），我們需要檢查所有可能的子串 s[j:i]（其中 j 從 0 到 i - 1），如果存在一個 j 使得 dp[j] 為 true 且子串 s[j:i] 存在于 wordDict 中，那么就可以得出 dp[i] = true。因為這意味著前 j 個字符可以被拆分，且從 j 到 i 的子串也在字典中，所以前 i 個字符也可以被拆分。
3. 最終結果：
   • 最終，dp[s.length] 的值就表示整個字符串 s 是否可以被拆分成 wordDict 中的單詞。

復雜度分析

• 時間復雜度：$O(n^2?m)$，其中 $n$ 是字符串 s 的長度，$m$ 是字典 wordDict 的長度。對于每個位置 i，需要遍歷所有可能的子串，時間復雜度為