hard

Concatenated Words

Find every word that is made by gluing together two or more shorter words from the same list, using a trie to try each split point.

1. Define the problem

Concatenated Words

You are given a list of words, all different from one another. Return every word that is a concatenated word : a word made entirely by gluing together two or more shorter words that are also in the same list. For example, if the list contains "cat", "dog" and "catdog", then "catdog" is a concatenated word because it is exactly "cat" followed by "dog". Put every word into a trie. Then, for each word, walk its letters down the trie from the start. Every time you pass an end-of-word marker you have found one possible first piece, so you go back to the root and try to split the rest of the word the same way. That is a recursive search over split points . The word only counts if the pieces run out exactly at the end AND at least two pieces were used — otherwise every word would trivially match itself. Remembering which start positions already failed stops the search from redoing the same work over and over on long words.

Constraints

  • 1 ≤ words.length ≤ 104
  • 1 ≤ wordsi.length ≤ 30
  • wordsi consists of lowercase English letters only
  • All the words are different from one another

Example

Inputwords = ["cat", "cats", "catsdog", "dog"]
Output["catsdog"]

Explanation "catsdog" splits into "cats" and "dog", both of which are in the list, so it is returned. "cat", "cats" and "dog" are each only one piece long, so they do not count.

2. Know the words first

In plain terms

Concatenation
Gluing strings together end to end. "cat" concatenated with "dog" is "catdog".
Split point
A position where you cut the word into a finished piece and a remaining part still to be checked.
Memoisation
Writing down answers you already worked out so you never compute them twice. Here, the start positions that were already shown to fail.
End-of-word marker
A true/false flag on a trie node meaning "one of the stored words finishes right here".
3. Visualize the solution

Splitting "catsdog" using a trie of cat, cats and dog

Splitting "catsdog" using a trie of cat, cats and dog
Statusinit

The words cat, cats and dog are stored in the trie; now test "catsdog".

What happens in this step

words = ["cat", "cats", "catsdog", "dog"]
testing word = 'catsdog'
canSplit(word, start = 0, pieces = 0)

The word itself is also in the trie, but matching the whole thing gives only one piece.
Step 1 of 7

Steps to visualize

  1. The row of cells is the word being tested, one cell per letter.
  2. The value shows what the walk found at that letter: "node" means the path continues, "word!" means a piece can end there, "none" means the trie ran out.
  3. When a piece ends, the search jumps back to the root and keeps going from the next letter.
  4. A dead end simply backs up and tries the next possible split point instead.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Splitting "catsdog" using a trie of cat, cats and dog
Statusinit

The words cat, cats and dog are stored in the trie; now test "catsdog".

What happens in this step

words = ["cat", "cats", "catsdog", "dog"]
testing word = 'catsdog'
canSplit(word, start = 0, pieces = 0)

The word itself is also in the trie, but matching the whole thing gives only one piece.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function findAllConcatenatedWordsInADict(words) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  const root = new TrieNode();

  for (const word of words) {
    if (word.length === 0) {
      continue;
    }

    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  const canSplit = (word, start, pieces, seen) => {
    if (start === word.length) {
      return pieces >= 2;
    }

    if (seen.has(start)) {
      return false;
    }

    let node = root;

    for (let i = start; i < word.length; i++) {
      node = node.children[word[i]];
      if (!node) {
        break;
      }
      if (node.isEnd && canSplit(word, i + 1, pieces + 1, seen)) {
        return true;
      }
    }

    seen.add(start);
    return false;
  };

  const answer = [];

  for (const word of words) {
    if (word.length > 0 && canSplit(word, 0, 0, new Set())) {
      answer.push(word);
    }
  }

  return answer;
}
Time
O(n * L^2) where n is the number of words and L the longest word length
Space
O(total letters across all words)
6. Test cases

Test cases

InputExpectedCovers
words = ["cat", "cats", "catsdog", "dog"]["catsdog"]example from the docstring
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]["catsdogcats", "dogcatsdog", "ratcatdogcat"]several concatenated words mixed in with words that are not
words = ["abc", "def"][]no word can be built from the others
words = ["cat"][]a word never counts as a concatenation of just itself
words = ["a", "aa", "aaa"]["aa", "aaa"]the same short word reused as several pieces
words = ["", "a", "ab", "b"]["ab"]an empty word must be ignored, not treated as a free piece

Keep reading