题目如下：
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Note:
- The number of elements of the given array will not exceed
10,000- The length sum of elements in the given array will not exceed
600,000.- All the input string will only include lower case letters.
- The returned elements order does not matter.
解题思路：我的方法是Input按单词的长度升序排序后存入字典树中，因为Input中单词不重复，所有较长的单词肯定是由比其短的单词拼接而成的。每个单词在存入字典树的时候，同时做前缀匹配，并保存匹配的结果，接下来再对这些结果递归做前缀匹配，直到无法匹配或者完全匹配为止。如果有其中任意一个结果满足完全匹配，则表示这个单词可以由其他的单词拼接而成。
代码如下：
class TreeNode(object): def __init__(self, x): self.val = x self.childDic = {} self.hasWord = Falseclass Trie(object): dic = {} def __init__(self): """ Initialize your data structure here. """ self.root = TreeNode(None) self.dic = {} def divide(self, word,flag): substr = [] current = self.root path = '' for i in word: path += i if i not in current.childDic: current.childDic[i] = TreeNode(i) current = current.childDic[i] if current.hasWord: substr.append(word[len(path):]) self.dic[path] = 1 if flag: self.dic[word] = 1 current.hasWord = True return substr def isExist(self,w): return w in self.dicclass Solution(object): def findAllConcatenatedWordsInADict(self, words): """ :type words: List[str] :rtype: List[str] """ words.sort(cmp=lambda x1,x2:len(x1) - len(x2)) t = Trie() res = [] for w in words: queue = t.divide(w,True) while len(queue) > 0: item = queue.pop(0) if t.isExist(item): res.append(w) #t.dic[w] = 1 break else: queue += t.divide(item,False) return res