472. Concatenated Words
Đề Bài
Given an array of strings words (without duplicates), return all the 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 1:
Input: words = ["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".
Example 2:
Input: words = ["cat","dog","catdog"] Output: ["catdog"]
Constraints:
1 <= words.length <= 1041 <= words[i].length <= 30words[i]consists of only lowercase English letters.- All the strings of
wordsare unique. 1 <= sum(words[i].length) <= 105
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
Python
0472-concatenated-words.py
class Node:
def __init__(self):
self.char = ''
self.isEndWord = False
self.children = defaultdict(Node)
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
root = self.root
for char in word:
root = root.children[char]
root.isEndWord = True
def find(self, word: str) -> int:
root = self.root
for char in word:
if char not in root.children:
return False
root = root.children[char]
return root.isEndWord
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
trie = Trie()
for word in words:
trie.insert(word)
@cache
def dfs(i, n, word, cnt):
root = trie.root
for j in range(i, n):
if word[j] not in root.children:
return False
root = root.children[word[j]]
if root.isEndWord:
if j == n - 1:
return cnt >= 1
elif dfs(j + 1, n, word, cnt + 1):
return True
return False
ans = []
for word in words:
if dfs(0, len(word), word, 0):
ans.append(word)
return ans