2021-05-22：假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。

2021-05-22：假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。

福大大 答案2021-05-22：

前缀树。时间复杂度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]

}

执行结果如下：

左神java代码

2021-05-22：假设所有字符都是小写字母， 大字符串是str，arr是去重的单词表， 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式。 返回方法数。的相关教程结束。