Compound Word Finder
HardTries & Strings
Problem
A dictionary editor wants to flag compound entries. Given a list of distinct non-empty words, return every word that can be written as a concatenation of two or more other words from the list (words may be reused).
Return them in the order they appear in words.
Example 1
- Input:
- words = ["cat","cats","dog","catsdog","dogcat","rat","catdograt","hippo"]
- Output:
- ["catsdog","dogcat","catdograt"]
catsdog = cats + dog, dogcat = dog + cat, catdograt = cat + dog + rat.
Example 2
- Input:
- words = ["a","aa","aaa"]
- Output:
- ["aa","aaa"]
"a" may be reused: aa = a + a.
Example 3
- Input:
- words = ["sun","flower","sunflowers"]
- Output:
- []
Constraints
- 1 ≤ words.length ≤ 10^4
- 1 ≤ words[i].length ≤ 30
- Sum of lengths ≤ 10^5
- Lowercase English letters; words are distinct.
Hint
Show the first hint
A word can only be built from strictly shorter words. Which order of processing makes that easy?
Walkthrough
How to approach it
01Clarify before coding
- Can a part be reused? Yes, "a" + "a" is fine.
- Can a word use itself as a part? No: it must be two or more words, so each part is shorter.
- Output order? The order of the input.
02Brute force
For each word, try every way to split it recursively against the full set of words.
Cost: Exponential without memoisation: "aaaa...ab" against {a, aa} explores about 2^L splits per word.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.