假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。
前缀树。时间复杂度O(N2)。传统方法的时间复杂度是O(N3)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "aaab"
arr := []string{"a", "aa", "aaa", "ab", "b"}
ret := ways4(s, arr)
fmt.Println(ret)
}
type Node struct {
end bool
nexts []*Node
}
func NewNode() *Node {
ans := &Node{}
ans.nexts = make([]*Node, 26)
return ans
}
func ways4(s string, arr []string) int {
if len(s) == 0 || len(arr) == 0 {
return 0
}
root := NewNode()
for _, str := range arr {
node := root
index := 0
for i := 0; i < len(str); i++ {
index = int(str[i] - 'a')
if node.nexts[index] == nil {
node.nexts[index] = NewNode()
}
node = node.nexts[index]
}
node.end = true
}
N := len(s)
dp := make([]int, N+1)
dp[N] = 1
for i := N - 1; i >= 0; i-- {
cur := root
for end := i; end < N; end++ {
path := int(s[end] - 'a')
if cur.nexts[path] == nil {
break
}
cur = cur.nexts[path]
if cur.end {
dp[i] += dp[end+1]
}
}
}
return dp[0]
}执行结果如下：
