单词拆分。给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。力扣139。
自然智慧。从左往右尝试，用前缀树。如果没路了，就不需要试了。
时间复杂度：O(N)。
额外空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
if true {
s := "leetcode"
wordDict := []string{"leet", "code"}
ret := wordBreak1(s, wordDict)
fmt.Println(ret)
}
if true {
s := "leetcode"
wordDict := []string{"leet", "code"}
ret := wordBreak2(s, wordDict)
fmt.Println(ret)
}
}
type Node struct {
end bool
nexts []*Node
}
func NewNode() *Node {
res := &Node{}
res.end = false
res.nexts = make([]*Node, 26)
return res
}
func wordBreak1(s string, wordDict []string) bool {
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.end = true
}
str := []byte(s)
N := len(str)
dp := make([]bool, N+1)
dp[N] = true // dp[i] word[i.....] 能不能被分解
// dp[N] word[N...] -> "" 能不能够被分解
// dp[i] ... dp[i+1
for i := N - 1; i >= 0; i-- {
// i
// word[i....] 能不能够被分解
// i..i i+1....
// i..i+1 i+2...
cur := root
for end := i; end < N; end++ {
cur = cur.nexts[str[end]-'a']
if cur == nil {
break
}
// 有路！
if cur.end {
// i...end 真的是一个有效的前缀串 end+1.... 能不能被分解
dp[i] = dp[i] || dp[end+1]
}
if dp[i] {
break
}
}
}
return dp[0]
}
func wordBreak2(s string, wordDict []string) int {
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.end = true
}
str := []byte(s)
N := len(str)
dp := make([]int, N+1)
dp[N] = 1
for i := N - 1; i >= 0; i-- {
cur := root
for end := i; end < N; end++ {
cur = cur.nexts[str[end]-'a']
if cur == nil {
break
}
if cur.end {
dp[i] += dp[end+1]
}
}
}
return dp[0]
}执行结果如下：
