Concatenated Word List Problem

Concatenated Word List Problem — ExecCode Hard DSA Practice

Solve the Concatenated Word List problem on ExecCode. Free online hard DSA practice in String. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A concatenated word is a word that can be built by joining at least two shorter words from the same list. This is Word Break on every word using the rest of the dictionary, a frequent Amazon OA hard follow-up. Return every concatenated word, sorted lexicographically. You are given: words — unique strings Return sorted list of strings that are concatenations of other words in the list. Do not use the word itself as its only piece.

Examples

Input {'words': ['cat', 'cats', 'catsdogcats', 'dog', 'dogcatsdog', 'hippopotamuses', 'rat', 'ratcatdogcat']}; Output ['catsdogcats', 'dogcatsdog', 'ratcatdogcat']. Input {'words': ['cat', 'dog', 'catdog']}; Output ['catdog']. Input {'words': ['a', 'b', 'ab', 'abc']}; Output ['ab']

Constraints

A word must use at least two pieces Pieces must appear exactly as dictionary words

Practice Concatenated Word List free on ExecCode. Browse DSA problems, topic map, and placement guides.