Concatenated Words

Implement findAllConcatenatedWords

Given a list of distinct words, return every word that can be built by concatenating at least two other, shorter words from the same list — reusing a word as many times as needed, in any order. This is Word Break run once per word, with the rest of the same list playing the role of the dictionary — a word "counts" exactly when it's fully covered by pieces drawn from the shared trie. The only wrinkle: the word trivially "matches itself" as a single whole piece, and that doesn't count as a real concatenation, so that one specific match — the entire word, taken in one bite, starting from position zero — gets explicitly excluded. Everything else about the reachability walk is identical to Word Break.

Example 1:

Input: words = ["cat","cats","catsdog","dog"]

Output: ["catsdog"]

Example 2:

Input: words = ["cat","dog","catdog","catdogcat"]

Output: ["catdog","catdogcat"]

Example 3:

Input: words = ["a","b","ab","abc","c"]

Output: ["ab","abc"]

+ 10 hidden test cases run on Submit.

Constraints:

  • 0 ≤ words.length ≤ 200
  • 1 ≤ words[i].length ≤ 30
  • words consists of lowercase English letters, and every entry is distinct

words =

["cat", "cats", "catsdog", "dog"]