Coding Interview PatternsConcatenated Words
HardTrie

Concatenated Words

Explanation & Solution

Practice Problem

Description

Given an array of strings words (without duplicates), return all the concatenated words in the given list.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) from the given array.

Input:words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
0
cat
1
cats
2
catsdogcats
3
dog
4
dogcatsdog
5
hippopotamuses
6
rat
7
ratcatdogcat
Output:["catsdogcats","dogcatsdog","ratcatdogcat"]
0
catsdogcats
1
dogcatsdog
2
ratcatdogcat

Explanation: "catsdogcats" can be formed by "cats" + "dog" + "cats". "dogcatsdog" can be formed by "dog" + "cats" + "dog". "ratcatdogcat" can be formed by "rat" + "cat" + "dog" + "cat".

Constraints

  • 1 <= words.length <= 10⁴
  • 1 <= words[i].length <= 30
  • words[i] consists of only lowercase English letters
  • All the strings of words are unique

Approach

Trie pattern

1. Sort Words by Length

  • Sort the array so shorter words come first
  • This ensures that when we check if a word is concatenated, all its potential component words are already in the trie

2. Build a Trie Incrementally

  • Process words from shortest to longest
  • For each word, first check if it can be formed from existing words in the trie
  • Then insert the word into the trie

3. Recursive Check with Trie

  • For each word, use a recursive function canForm(word, index, count) to check if it can be split into at least 2 words from the trie
  • Starting from index, traverse the trie character by character
  • Whenever we reach a node marked as _end, we found a complete word — recursively check the remainder of the string
  • If we reach the end of the word with count >= 2, it is a valid concatenated word

4. Collect Results

  • If a word can be formed by at least two shorter words, add it to the result array
  • After checking, insert the word into the trie so it can be used by longer words

Key Insight

  • Sorting by length and building the trie incrementally ensures we only check against shorter words. The trie enables efficient prefix matching at each recursive step, avoiding repeated string comparisons.
Time
O(N * L²) where N is the number of words and L is the max word length
Space
O(N * L) for the trie

Solution Code

Previous
Stream of Characters
Next
Count Prefix and Suffix Pairs