Scale Engineer

Concatenated Words

Hard
#0459Time: O(N * 2^L). For each of the N words, the `canBreak` function can take exponential time in the worst case, roughly O(2^L), where L is the length of the word. The set modifications take O(L) each.Space: O(N * L + L). O(N * L) for storing the dictionary set, where N is the number of words and L is the average word length. O(L) for the recursion stack depth.1 company
Patterns
Dynamic Programming
Algorithms
Depth-First Search
Data structures
ArrayStringTrie
Companies
eBay

Prompt

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 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 <= 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach checks each word in the input list to see if it can be formed by concatenating other words from the list. For every word, it uses a standard brute-force recursive method to solve the 'Word Break' problem. The dictionary for the word break check consists of all other words in the list.

Algorithm

  • For each word in the input array words:
    • Create a dictionary Set containing all words from the input array except for the current word.
    • Call a recursive helper function canBreak(current_word, dictionary) to check if the current_word can be segmented into a sequence of one or more words from the temporary dictionary.
    • The canBreak(s, dict) function works as follows:
      • Base Case: If s is empty, it means the previous prefix was a valid word, so return true.
      • Recursive Step: Iterate from i = 1 to s.length(). Split s into prefix = s.substring(0, i) and suffix = s.substring(i).
      • If prefix is in the dict and canBreak(suffix, dict) returns true, then s can be broken down. Return true.
      • If the loop completes without finding a valid break, return false.
    • If canBreak returns true, add the word to the result list.

Walkthrough

The fundamental idea is to treat this as a series of 'Word Break' problems. For each word, we want to determine if it can be segmented using a dictionary composed of the other words in the list. This ensures that the word is formed by at least two shorter words.

The brute-force recursion explores all possible ways to segment a word. For a word s, it tries every possible prefix. If a prefix is a valid word in the dictionary, it recursively calls itself on the remaining suffix. This process continues until the suffix is empty (a successful segmentation) or all possibilities are exhausted.

Because this method does not store the results of subproblems (e.g., whether a particular suffix can be segmented), it re-computes the same information multiple times, leading to an exponential time complexity.

public List<String> findAllConcatenatedWordsInADict(String[] words) {    List<String> result = new ArrayList<>();    Set<String> dictionary = new HashSet<>(Arrays.asList(words));     for (String word : words) {        dictionary.remove(word); // Temporarily remove the word itself        if (canBreak(word, dictionary)) {            result.add(word);        }        dictionary.add(word); // Add it back for the next iteration    }    return result;} private boolean canBreak(String s, Set<String> dictionary) {    if (s.isEmpty()) {        return true; // Successfully segmented    }     // Check every possible prefix    for (int i = 1; i <= s.length(); i++) {        String prefix = s.substring(0, i);        if (dictionary.contains(prefix)) {            // If prefix is a word, recursively check the rest of the string            if (canBreak(s.substring(i), dictionary)) {                return true;            }        }    }     return false; // No segmentation found}

Complexity

Time

O(N * 2^L). For each of the N words, the `canBreak` function can take exponential time in the worst case, roughly O(2^L), where L is the length of the word. The set modifications take O(L) each.

Space

O(N * L + L). O(N * L) for storing the dictionary set, where N is the number of words and L is the average word length. O(L) for the recursion stack depth.

Trade-offs

Pros

  • Simple to understand and implement the recursive logic.

Cons

  • Extremely inefficient due to the lack of memoization.

  • The number of recursive calls grows exponentially with the length of the word, leading to a 'Time Limit Exceeded' error on most platforms.

  • Repeatedly computes the result for the same subproblems.

Solutions

class Trie { Trie [] children = new Trie [ 26 ]; boolean isEnd ; void insert ( String w ) { Trie node = this ; for ( char c : w . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; } node . isEnd = true ; } } class Solution { private Trie trie = new Trie (); public List < String > findAllConcatenatedWordsInADict ( String [] words ) { Arrays . sort ( words , ( a , b ) -> a . length () - b . length ()); List < String > ans = new ArrayList <>(); for ( String w : words ) { if ( dfs ( w )) { ans . add ( w ); } else { trie . insert ( w ); } } return ans ; } private boolean dfs ( String w ) { if ( "" . equals ( w )) { return true ; } Trie node = trie ; for ( int i = 0 ; i < w . length (); ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { return false ; } node = node . children [ idx ]; if ( node . isEnd && dfs ( w . substring ( i + 1 ))) { return true ; } } return false ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem