单词拆分II——可达性DP+回溯+哈希表

这道题，我们需要先通过把单词录入哈希表。

然后构造一个可达性DP，dp[i] 代表了 s[0..i] 是否能拆分成 wordsDict 中的单词，再通过可达性 DP 构造一个 prevs 数组记录从某个位置 j 能够构造出的多个单词起点 i 的关系图。

最后通过回溯 DFS，从尾部开始向前搜索 prevs 数组，一直遍历到头，得到的 path 一定是一个涵盖 wordsDict 单词的句子，并且因为可达性 DP 构造出的 prevs 数组提供了所有可能性，所以最终答案就这样出来了。

```go
func wordBreak(s string, wordDict []string) []string {
    n := len(s)
    dict := map[string]bool{}
    for _, word := range wordDict {
        dict[word] = true
    }
    // dp[i] = s[0..i] 能否切分单词
    dp := make([]bool, n+1)
    // prevs 统计 j 位置对应切分到多个单词的起始位置
    prevs := make([][]int, n+1)
    dp[0] = true
    for j := 1; j <= n; j++ {
        for i := 0; i < j; i++ {
            if dp[i] && dict[s[i:j]] {
                dp[j] = true
                prevs[j] = append(prevs[j], i)
            }
        }
    }
    if !dp[n] {
        // 按理说按照题意肯定s能被完整且分成所有的单词组合的
        return nil
    }
    res := []string{}
    path := []string{}
    var dfs func(end int)
    dfs = func(end int) {
        if end == 0 {
            tmp := make([]string, 0, len(path))
            for i := len(path)-1; i >= 0; i-- {
                tmp = append(tmp, path[i])
            }
            res = append(res, strings.Join(tmp, " "))
        }
        for _, prev := range prevs[end] {
            path = append(path, s[prev:end])
            dfs(prev)
            path = path[:len(path)-1]
        }
    }
    dfs(n)
    return res
}
```

Last modification：July 13, 2025