Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 472 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 472 # by problem number
lcpy gen -s concatenated_words # by problem name
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 (not necessarily distinct) in the given array.
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".
Input: words = ["cat","dog","catdog"]
Output: ["catdog"]
1 <= words.length <= 10^41 <= words[i].length <= 30words[i] consists of only lowercase English letters.words are unique.1 <= sum(words[i].length) <= 10^5class Solution:
# Time: O(n * m^2) where n = len(words), m = max word length
# Space: O(n * m)
def find_all_concatenated_words_in_a_dict(self, words: list[str]) -> list[str]:
word_set = set(words)
def can_form(word: str) -> bool:
n = len(word)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if not dp[j]:
continue
if j == 0 and i == n:
continue
if word[j:i] in word_set:
dp[i] = True
break
return dp[n]
return [word for word in words if can_form(word)]
| Time | Space |
|---|---|
| O(n * m^2) where n = len(words), m = max word length | O(n * m) |