LeetCode Word Break II：DFS + 備忘錄優化

LeetCode 140 Word Break II - 返回所有合法分詞句子

給定字符串 s 和詞典 dict，在 s 中加空格使每個詞都在詞典中，返回所有可能句子。

DFS 回溯 + 剪枝

遞歸函數 dfs(start, path)：

• start：當前處理位置
• path：已構建的詞列表
• 終止：start == n，將 path 合併為句子加入結果
• 嘗試所有 end = start+1..n，若 s[start..end-1] ∈ dict，加入 path 遞歸，回溯彈出

關鍵優化：先判斷可行性

直接 DFS 會在不可分割的字符串上大量無效遞歸導致 TLE。先用 Word Break I 的 DP 判斷 s 是否可分割，不可則直接返回空。

代碼

public List wordBreak(String s, Set dict) {
    List res = new ArrayList<>();
    if (!canBreak(s, dict)) return res; // 關鍵剪枝
    dfs(s, 0, "", dict, res);
    return res;
}
void dfs(String s, int start, String path, Set dict, List res) {
    if (start == s.length()) { res.add(path); return; }
    for (int end=start+1; end<=s.length(); ++end) {
        String word = s.substring(start, end);
        if (dict.contains(word)) {
            String newPath = path.isEmpty() ? word : path + " " + word;
            dfs(s, end, newPath, dict, res);
        }
    }
}
boolean canBreak(String s, Set dict) {
    boolean[] dp = new boolean[s.length()+1];
    dp[0] = true;
    for (int i=1; i<=s.length(); ++i)
        for (int j=0; j

進階：備忘錄記錄不可分割位置
在 DFS 中記錄 memo[start] = false 表示從 start 開始無法完成分割，避免重複探索死路。但 canBreak 預檢通常已足夠。

複雜度
輸出敏感。最壞情況（如 s="aaaa...", dict={"a","aa","aaa"}）指數級輸出量，但預檢能過濾無解情況。