Leecode #472. 连接词

给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

示例

输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]

解释: "catsdogcats"由"cats", "dog" 和 "cats"组成; 
     "dogcatsdog"由"dog", "cats"和"dog"组成; 
     "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。

解题思路

一开始想到用哈希保存单词前2个前缀+dfs的算法，然而效率很低。看到题解有一种类似的解法，不过是用set来保存以及遍历过的单词，技巧在于先排序从短到长遍历，速度很快

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        words = sorted(words, key=len)
        prefix = set()
        
        def dfs(word, begin, count=0):
            if word[begin:] in prefix:
                return True
            for i in range(len(word), begin, -1):
                if word[begin:i] in prefix and dfs(word, i, count+1):
                    return True
            return False
        rlt = []
        for word in words:
            if dfs(word, 0):
                rlt.append(word)
            prefix.add(word)
            # 每次遍历完单词后，add 进prefix
        return rlt