How do you solve Concatenated Words on LeetCode?

Concatenated Words (LeetCode #472) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * m²) time complexity and O(n * m) space complexity. Key insight: Using a Trie allows for efficient prefix searching, which is crucial for this problem.

What is the brute force solution for Concatenated Words?

The brute force approach for Concatenated Words is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every word to see if it can be formed by concatenating other words from the list. This is straightforward but inefficient, as it involves checking all possible combinations. The optimal Optimal Solution approach improves this to O(n * m²).

What are the interview tips for Concatenated Words?

Explain your thought process clearly as you work through the problem. Consider discussing both brute force and optimized approaches during the interview. Practice writing clean and efficient code, as readability is important.

What are common mistakes when solving Concatenated Words?

Not considering edge cases where words can overlap. Failing to optimize the search process, leading to timeouts on larger inputs.

#472

Concatenated Words

Hard

ArrayStringDynamic ProgrammingDepth-First SearchTrieSortingTrieDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * m²)
Space	O(1)	O(n * m)

💡

Intuition

Time O(n * m²)Space O(n * m)

The optimal solution uses dynamic programming and a Trie to efficiently check if a word can be formed by concatenating other words. This reduces the number of checks needed and speeds up the process significantly.

⚙️

Algorithm

3 steps

1Step 1: Insert all words into a Trie for fast prefix lookups.
2Step 2: For each word, use dynamic programming to check if it can be formed by concatenating other words in the Trie.
3Step 3: Maintain a DP array where dp[i] is true if the substring word[0:i] can be formed by concatenating words from the Trie.

solution.py48 lines

1# Full working Python code
2class TrieNode:
3    def __init__(self):
4        self.children = {}
5        self.is_end = False
6
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10
11    def insert(self, word):
12        node = self.root
13        for char in word:
14            if char not in node.children:
15                node.children[char] = TrieNode()
16            node = node.children[char]
17        node.is_end = True
18
19    def search(self, word):
20        node = self.root
21        for char in word:
22            if char not in node.children:
23                return False
24            node = node.children[char]
25        return node.is_end
26
27def can_form(word, trie):
28    dp = [False] * (len(word) + 1)
29    dp[0] = True
30    for i in range(1, len(word) + 1):
31        for j in range(i):
32            if dp[j] and trie.search(word[j:i]):
33                dp[i] = True
34                break
35    return dp[len(word)]
36
37def find_concatenated_words(words):
38    trie = Trie()
39    for word in words:
40        trie.insert(word)
41    concatenated_words = []
42    for word in words:
43        if can_form(word, trie):
44            concatenated_words.append(word)
45    return concatenated_words
46
47words = ['cat', 'cats', 'catsdogcats', 'dog', 'dogcatsdog', 'hippopotamuses', 'rat', 'ratcatdogcat']
48print(find_concatenated_words(words))

ℹ

Complexity note: The time complexity is O(n * m²) where n is the number of words and m is the maximum length of a word. This is due to checking all substrings for each word. The space complexity is O(n * m) because we store all words in the Trie.

1Using a Trie allows for efficient prefix searching, which is crucial for this problem.
2Dynamic programming helps to break down the problem into smaller subproblems, making it easier to solve.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.