本文詳細解析LeetCode 139題"單詞拆分"的動態規劃解法，涵蓋核心思路、代碼實現、區間理解和性能優化

問題描述

給定一個字符串 s 和一個字符串字典 wordDict，判斷 s 是否能被拆分為一個或多個字典中單詞的空格分隔序列。注意：字典中的單詞可以重復使用。

示例：

輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: "leetcode" 可拆分為 "leet code"

動態規劃解法

解法核心思路

使用動態規劃數組 valid，其中：

• valid[i] 表示字符串 s 的前 i 個字符（s.substring(0, i)）能否被拆分為字典中的單詞
• 目標是計算 valid[s.length()]（整個字符串是否可拆分）

完整代碼實現

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 將字典轉換為HashSet以提高查找效率HashSet<String> set = new HashSet<>(wordDict);// 創建動態規劃數組，長度+1（包含空字符串情況）boolean[] valid = new boolean[s.length