题目描述：

LeetCode 472. Concatenated Words

Given a list of words, 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:

1. The number of elements of the given array will not exceed `10,000 `
2. The length sum of elements in the given array will not exceed `600,000`.
3. The returned elements order does not matter.

题目大意：

1. 数组长度不会超过10000
2. 单词总长度不会超过600000
3. 返回结果的顺序无所谓

Python代码：

``````class Solution(object):
"""
:type words: List[str]
:rtype: List[str]
"""
ans = []
self.wordSet = set(words)
for word in words:
self.wordSet.remove(word)
if self.search(word):
ans.append(word)
return ans

def search(self, word):
if word in self.wordSet:
return True
for idx in range(1, len(word)):
if word[:idx] in self.wordSet and self.search(word[idx:]):
return True
return False
``````

LeetCode OJ放宽了Python的内存和时长限制，下面的代码可以通过系统测试。

Python代码：

``````class Solution(object):
"""
:type words: List[str]
:rtype: List[str]
"""
self.trie = Trie()
ans = []
for word in words:
self.trie.insert(word)
for word in words:
if self.search(word):
ans.append(word)
return ans

def search(self, word):
node = self.trie.root
for idx, letter in enumerate(word):
node = node.children.get(letter)
if node is None:
return False
suffix = word[idx+1:]
if node.isWord and (self.trie.search(suffix) or self.search(suffix)):
return True
return False

class TrieNode:
def __init__(self):
self.children = dict()
self.isWord = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for letter in word:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
node = child
node.isWord = True

def search(self, word):
node = self.root
for letter in word:
node = node.children.get(letter)
if node is None:
return False
return node.isWord
``````

Pingbacks已关闭。

1. Ice 发布于 2016年12月25日 10:35 #

看您写的代码是一种享受，简洁明了。

2. buri 发布于 2017年1月3日 16:57 #

是的呀，C++用Trie也MLE了，卡在最后一组T^T。。。然而直接搜和直接dp复杂度爆炸却给过了。。。。不是很懂LEETCODE