单词拆分 II。给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明：分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。力扣140。
具体见代码。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "catsanddog"
wordDict := []string{"cat", "cats", "and", "sand", "dog"}
ret := wordBreak(s, wordDict)
fmt.Println(ret)
}
type Node struct {
path0 string
end bool
nexts []*Node
}
func NewNode() *Node {
res := &Node{}
res.end = false
res.nexts = make([]*Node, 26)
return res
}
func wordBreak(s string, wordDict []string) []string {
str := []byte(s)
root := gettrie(wordDict)
dp := getdp(s, root)
path0 := make([]string, 0)
ans := make([]string, 0)
process(str, 0, root, dp, &path0, &ans)
return ans
}
// str[index.....] 是要搞定的字符串
// dp[0...N-1] 0... 1.... 2... N-1... 在dp里
// root 单词表所有单词生成的前缀树头节点
// path str[0..index-1]做过决定了，做的决定放在path里
func process(str []byte, index int, root *Node, dp []bool, path0 *[]string, ans *[]string) {
if index == len(str) {
builder := make([]byte, 0)
for i := 0; i < len((*path0))-1; i++ {
builder = append(builder, []byte(fmt.Sprintf("%s", (*path0)[i])+" ")...)
}
builder = append(builder, []byte(fmt.Sprintf("%s", (*path0)[len((*path0))-1])+" ")...)
*ans = append(*ans, string(builder))
} else {
cur := root
for end := index; end < len(str); end++ {
// str[i..end] （能不能拆出来）
road := str[end] - 'a'
if cur.nexts[road] == nil {
break
}
cur = cur.nexts[road]
if cur.end && dp[end+1] {
// [i...end] 前缀串
// str.subString(i,end+1) [i..end]
*path0 = append(*path0, cur.path0)
process(str, end+1, root, dp, path0, ans)
*path0 = (*path0)[0 : len((*path0))-1]
}
}
}
}
func gettrie(wordDict []string) *Node {
root := NewNode()
for _, str := range wordDict {
chs := []byte(str)
node := root
index := 0
for i := 0; i < len(chs); i++ {
index = int(chs[i] - 'a')
if node.nexts[index] == nil {
node.nexts[index] = NewNode()
}
node = node.nexts[index]
}
node.path0 = str
node.end = true
}
return root
}
func getdp(s string, root *Node) []bool {
str := []byte(s)
N := len(str)
dp := make([]bool, N+1)
dp[N] = true
for i := N - 1; i >= 0; i-- {
cur := root
for end := i; end < N; end++ {
path := str[end] - 'a'
if cur.nexts[path] == nil {
break
}
cur = cur.nexts[path]
if cur.end && dp[end+1] {
dp[i] = true
break
}
}
}
return dp
}执行结果如下：
