Words Built From Shorter Words

Hard

You are given a list dictionary of distinct words. Find every word in it that can be written out exactly by joining at least two other words from the same list end to end. A word may be used more than once. Return the words you find in any order.

Example 1

dictionary=['sun', 'flower', 'sunflower', 'pot', 'flowerpot', 'sunflowerpot', 'rain'] → ['sunflower', 'flowerpot', 'sunflowerpot']

sunflower = sun + flower, flowerpot = flower + pot, sunflowerpot = sun + flower + pot. The word rain cannot be built from the others.

Example 2

dictionary=['ha', 'hahaha', 'hah'] → ['hahaha']

hahaha = ha + ha + ha: the same word may be used several times. hah cannot be built.

Example 3

dictionary=['tree', 'house'] → []

Constraints

1 ≤ len(dictionary) ≤ 10⁴
1 ≤ len(dictionary[i]) ≤ 30
The total length of all words is at most 10⁵
Words consist of lowercase English letters and are all distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Trie Array String Dynamic Programming

Similar problems

Every Way to Space the Words Hard Phrase Rewrite Rules Hard Split Into Dictionary Words Medium Words Hidden in a Text Medium Outermost Folders Only Medium

Input

dictionary=['sun', 'flower', 'sunflower', 'pot', 'flowerpot', 'sunflowerpot', 'rain']

Expected

['sunflower', 'flowerpot', 'sunflowerpot']

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.