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 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
    }
}

执行结果如下：

左神java代码