题目描述:
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:
- 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
. - The returned elements order does not matter.
题目大意:
给定一组单词,编写程序返回所有由别的单词拼接而成的单词。
拼接是指至少由给定数组中的两个更短的单词组合。
注意:
- 数组长度不会超过10000
- 单词总长度不会超过600000
- 返回结果的顺序无所谓
解题思路:
解法I 深度优先搜索(Depth First Search)
Python代码:
class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
: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)
self.wordSet.add(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
解法II 字典树(Trie)
思路同前,使用字典树Trie替换Set,理论上可以提升查找效率。
然而,下面的代码返回MLE。o(╯□╰)o
LeetCode OJ放宽了Python的内存和时长限制,下面的代码可以通过系统测试。
Python代码:
class Solution(object):
def findAllConcatenatedWordsInADict(self, words):
"""
: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
本文链接:http://bookshadow.com/weblog/2016/12/18/leetcode-concatenated-words/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
Ice 发布于 2016年12月25日 10:35 #
看您写的代码是一种享受,简洁明了。
buri 发布于 2017年1月3日 16:57 #
是的呀,C++用Trie也MLE了,卡在最后一组T^T。。。然而直接搜和直接dp复杂度爆炸却给过了。。。。不是很懂LEETCODE