连接词。
给你一个 不含重复 单词的字符串数组 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。
前缀树，从左往右的尝试模型。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
words := []string{"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"}
ret := findAllConcatenatedWordsInADict2(words)
fmt.Println(ret)
}
type TrieNode struct {
end bool
nexts []*TrieNode
}
func NewTrieNode() *TrieNode {
ans := &TrieNode{}
ans.end = false
ans.nexts = make([]*TrieNode, 26)
return ans
}
func insert(root *TrieNode, s []byte) {
path0 := 0
for _, 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 := false
if i == len(s) {
ans = true
} else {
c := r
for 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 = true
break
}
}
}
dp[i] = twoSelectOne(ans, 1, -1)
return ans
}
func twoSelectOne(c bool, a, b int) int {
if c {
return a
} else {
return b
}
}执行结果如下：
