140. 单词拆分 II

题目描述

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意: 词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = “catsanddog”, wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

示例 2：

输入:s = “pineapplepenapple”, wordDict = [“apple”,“pen”,“applepen”,“pine”,“pineapple”]
输出:[“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:s = “catsandog”, wordDict = [“cats”,“dog”,“sand”,“and”,“cat”]
输出:[]

提示：

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

解法一：动态规划 + DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


func wordBreak(s string, wordDict []string) []string {
    n := len(s)
    set := make(map[string]struct{})
    for _, word := range wordDict {
        set[word] = struct{}{}
    }
    dp := make([]bool, n+1)
    dp[0] = true
    record := make(map[int][]int)
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if _, has := set[s[j:i]]; has && dp[j] {
                dp[i] = true
                record[i] = append(record[i], j)
            }
        }
    }
    if dp[n] == false {
        return []string{}
    }
    var dfs func(idx int)
    var separators []int
    var ans []string
    dfs = func(idx int) {
        if 0 == idx {
            sb := strings.Builder{}
            prev := 0
            for i := len(separators) - 1; i >= 0; i-- {
                sb.WriteString(s[prev:separators[i]])
                if i != 0 {
                    sb.WriteByte(' ')
                }
                prev = separators[i]
            }
            ans = append(ans, sb.String())
            return
        }
        separators = append(separators, idx)
        for _, next := range record[idx] {
            fmt.Println(next)
            dfs(next)
        }
        separators = separators[:len(separators)-1]
    }
    dfs(n)
    return ans
}

解法二：记忆化搜索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


func wordBreak(s string, wordDict []string) (sentences []string) {
    wordSet := map[string]struct{}{}
    for _, w := range wordDict {
        wordSet[w] = struct{}{}
    }

    n := len(s)
    dp := make([][][]string, n)
    var backtrack func(index int) [][]string
    backtrack = func(index int) [][]string {
        if dp[index] != nil {
            return dp[index]
        }
        wordsList := [][]string{}
        for i := index + 1; i < n; i++ {
            word := s[index:i]
            if _, has := wordSet[word]; has {
                for _, nextWords := range backtrack(i) {
                    wordsList = append(wordsList, append([]string{word}, nextWords...))
                }
            }
        }
        word := s[index:]
        if _, has := wordSet[word]; has {
            wordsList = append(wordsList, []string{word})
        }
        dp[index] = wordsList
        return wordsList
    }
    for _, words := range backtrack(0) {
        sentences = append(sentences, strings.Join(words, " "))
    }
    return
}