Golang | Leetcode Golang题解之第472题连接词

题目：

题解：

type trie struct {children [26]*trieisEnd    bool
}func (root *trie) insert(word string) {node := rootfor _, ch := range word {ch -= 'a'if node.children[ch] == nil {node.children[ch] = &trie{}}node = node.children[ch]}node.isEnd = true
}func (root *trie) dfs(vis []bool, word string) bool {if word == "" {return true}if vis[len(word)-1] {return false}vis[len(word)-1] = truenode := rootfor i, ch := range word {node = node.children[ch-'a']if node == nil {return false}if node.isEnd && root.dfs(vis, word[i+1:]) {return true}}return false
}func findAllConcatenatedWordsInADict(words []string) (ans []string) {sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })root := &trie{}for _, word := range words {if word == "" {continue}vis := make([]bool, len(word))if root.dfs(vis, word) {ans = append(ans, word)} else {root.insert(word)}}return
}