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"]