January 29, 2022: connectives. Give you an array of strings without repeated words

2022-01-29： Conjunctions .

To give you one Without repetition String array of words words , Please find out and return to words All in Conjunctions .

Conjunctions Defined as ： A string consisting entirely of at least two shorter words in a given array .

Input ：words = "cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"

Output ："catsdogcats","dogcatsdog","ratcatdogcat"

explain ："catsdogcats" from "cats", "dog" and "cats" form ;

 "dogcatsdog"  from  "dog", "cats"  and  "dog"  form ; 

 "ratcatdogcat"  from  "rat", "cat", "dog"  and  "cat"  form .

Power button 472.

answer 2022-01-29：

Prefix tree , Try the model from left to right .

The code to use golang To write . The code is as follows ：

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
}

//  Prepare the dynamic planning table in advance 
var dp = make([]int, 1000)

//  Method 2 ： Prefix tree optimization  +  Dynamic planning optimization 
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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code