#472

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Concatenated Words

Find concatenated words by using dynamic programming and depth-first search to identify valid words made of other words in the list.

array string dynamic programming depth first search trie

Problem Statement

Given a list of unique strings, return all words in the list that are formed by concatenating at least two other words from the same list. A concatenated word must be formed by joining shorter words from the array, not necessarily distinct.

For example, in the list ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses"], the words "catsdogcats", "dogcatsdog", and "ratcatdogcat" are valid concatenated words, while others are not. The challenge is to efficiently identify these concatenated words for large inputs, which requires careful handling of the problem's constraints.

Examples

Example 1

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

"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"]

Example details omitted.

Constraints

1 <= words.length <= 104
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 105

Solution Approach

Dynamic Programming Approach

Use dynamic programming (DP) to break down the problem into smaller subproblems. We create a DP table for each word and check if it can be formed by concatenating smaller words from the list. This solution requires iterating over substrings of a word to see if they exist in the set of words.

Trie Data Structure

A trie is built to store all the words in the list. This allows efficient lookup of substrings within the words. By combining the trie structure with dynamic programming, we can optimize the process of checking whether a word can be split into smaller valid words.

Depth-First Search

A depth-first search (DFS) can be used to traverse through the trie and check if a word can be decomposed into valid substrings that are also words in the list. This method is useful for ensuring that every potential split of a word is explored, making it an essential part of the solution.

Complexity Analysis

Metric	Value
Time	O(M ^ 3 \cdot N)
Space	O(N \cdot M)

The time complexity is O(M ^ 3 * N), where M is the maximum length of a word and N is the number of words. This accounts for checking every possible substring and validating it using dynamic programming or trie-based lookups. The space complexity is O(N * M), where N is the number of words and M is the average length of the words, due to storage of the trie and dynamic programming tables.

What Interviewers Usually Probe

Check if the candidate understands how to use dynamic programming and recursion together to optimize the search for concatenated words.
Look for knowledge of optimizing searches using trie data structures and recognizing when to use them for large-scale problems.
Assess if the candidate can handle word manipulations effectively, considering time and space complexities in relation to the problem's constraints.

Common Pitfalls or Variants

Common pitfalls

Not using a trie to optimize substring lookups, which can lead to inefficient solutions for large inputs.
Failing to properly handle words that can overlap, leading to incorrect results.
Using brute force methods without considering time complexity, which will lead to performance issues when the input list is large.

Follow-up variants

Implementing this problem using only dynamic programming without a trie.
Allowing a word to be formed from any subset of words (not just at least two) in the list.
Handling edge cases where a word might be a concatenation of its own prefix and suffix.

FAQ

What is the core approach for solving Concatenated Words?

The core approach is to use dynamic programming, depth-first search, and a trie to break down words and identify those that can be formed by concatenating other words in the list.

How can I optimize the solution for large input sizes?

Using a trie structure for efficient substring lookups and dynamic programming to minimize redundant calculations can help optimize the solution for large inputs.

What is the role of dynamic programming in this problem?

Dynamic programming helps break down the problem into smaller subproblems, checking if a word can be formed by concatenating smaller words from the list without recalculating the same results repeatedly.

Can this problem be solved without using a trie?

Yes, it can be solved using only dynamic programming, but a trie can significantly improve efficiency by enabling fast substring lookups.

What is the time complexity of the optimal solution?

The time complexity of the optimal solution is O(M ^ 3 * N), where M is the maximum word length and N is the number of words.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, w):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        def dfs(w):
            if not w:
                return True
            node = trie
            for i, c in enumerate(w):
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    return False
                node = node.children[idx]
                if node.is_end and dfs(w[i + 1 :]):
                    return True
            return False

        trie = Trie()
        ans = []
        words.sort(key=lambda x: len(x))
        for w in words:
            if dfs(w):
                ans.append(w)
            else:
                trie.insert(w)
        return ans

Continue Practicing

#792 number of matching subsequences #692 top k frequent words #720 longest word in dictionary