2022-01-29：连接词。 给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。 连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串

2022-01-29：连接词。
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
输入：words = [“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”]
输出：[“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]
解释：“catsdogcats” 由 “cats”, “dog” 和 “cats” 组成;
“dogcatsdog” 由 “dog”, “cats” 和 “dog” 组成;
“ratcatdogcat” 由 “rat”, “cat”, “dog” 和 “cat” 组成。
力扣472。

答案2022-01-29：

前缀树，从左往右的尝试模型。

代码用golang编写。代码如下：

package mainimport ("fmt""sort"
)func main() {words := []string{"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}ret := findAllConcatenatedWordsInADict2(words)fmt.Println(ret)
}type TrieNode struct {end   boolnexts []*TrieNode
}func NewTrieNode() *TrieNode {ans := &TrieNode{}ans.end = falseans.nexts = make([]*TrieNode, 26)return ans
}func insert(root *TrieNode, s []byte) {path0 := 0for _, c := range s {path0 = int(c - 'a')if root.nexts[path0] == nil {root.nexts[path0] = NewTrieNode()}root = root.nexts[path0]}root.end = true
}// 提前准备好动态规划表
var dp = make([]int, 1000)// 方法二：前缀树优化 + 动态规划优化
func findAllConcatenatedWordsInADict2(words []string) []string {ans := make([]string, 0)if len(words) < 3 {return ans}sort.Slice(words, func(i, j int) bool {str1 := words[i]str2 := words[j]return len(str1) < len(str2)})root := NewTrieNode()for _, str := range words {s := []byte(str)for i := 0; i < len(s)+1; i++ {dp[i] = 0}if len(s) > 0 && split2(s, root, 0, dp) {ans = append(ans, str)} else {insert(root, s)}}return ans
}func split2(s []byte, r *TrieNode, i int, dp []int) bool {if dp[i] != 0 {return dp[i] == 1}ans := falseif i == len(s) {ans = true} else {c := rfor end := i; end < len(s); end++ {path0 := s[end] - 'a'if c.nexts[path0] == nil {break}c = c.nexts[path0]if c.end && split2(s, r, end+1, dp) {ans = truebreak}}}dp[i] = twoSelectOne(ans, 1, -1)return ans
}func twoSelectOne(c bool, a, b int) int {if c {return a} else {return b}
}

执行结果如下：

左神java代码