How hard is LeetCode 472. Concatenated Words?

LeetCode 472. Concatenated Words is rated Hard on LeetCode.

What topics does LeetCode 472. Concatenated Words cover?

LeetCode 472. Concatenated Words is tagged Depth-First Search, Trie, Array, String, Dynamic Programming and Sorting on LeetCode.

Concatenated Words — LeetCode 472 Python Solution

HardDepth-First SearchTrieArrayStringDynamic ProgrammingSorting

Problem: #472
Pattern: Trie
Reading time: 7 min
Source: leetcode.com

The problem

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 (not necessarily distinct) in the given array.

Example

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 472. Concatenated Words is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 472. Concatenated Words?: LeetCode 472. Concatenated Words is rated Hard on LeetCode.
What topics does LeetCode 472. Concatenated Words cover?: LeetCode 472. Concatenated Words is tagged Depth-First Search, Trie, Array, String, Dynamic Programming and Sorting on LeetCode.