Quick Overview

Return every word in a list of distinct lowercase words that can be formed by joining two or more words from the same list, reusing words if needed, in input order. Tests splitting a string into dictionary words, fast set lookups, ordering work by word length, and efficiency on inputs with up to ten thousand words.

Find List Words Formed by Joining Two or More Other Words From the List

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of distinct lowercase words, return every word in the list that can be formed by joining two or more words from the same list end to end. ### Function Signature ```python def find_compound_words(words: list[str]) -> list[str]: ``` ### Rules - A word `w` in the list is compound when `w` equals the concatenation `p1 + p2 + ... + pm` for some `m >= 2`, where every piece `pi` is a word in the list. - The same word may be used as a piece more than once. Because there are at least two nonempty pieces, every piece is shorter than `w`, so a word never counts as a piece of itself. - Return the compound words in the order in which they appear in `words`. Return an empty list if there are none. ### Constraints - `1 <= len(words) <= 10^4` - `1 <= len(words[i]) <= 30` - The total length of all the words is at most `10^5`. - Every word consists of lowercase English letters, and all words are distinct. ### Examples **Example 1** ```text Input: words = ["sun", "flower", "sunflower", "flowers", "s", "sunflowers", "pot"] Output: ["sunflower", "flowers", "sunflowers"] ``` `"sunflower"` is `"sun" + "flower"`, `"flowers"` is `"flower" + "s"`, and `"sunflowers"` is `"sun" + "flower" + "s"` (or `"sun" + "flowers"`). None of the other words can be split into words from the list. **Example 2** ```text Input: words = ["ab", "abab", "aba", "b"] Output: ["abab"] ``` `"abab"` is `"ab" + "ab"`, using the same word twice. `"aba"` would need the remaining piece `"a"`, which is not in the list, and `"ab"` would need `"a" + "b"`. **Example 3** ```text Input: words = ["x", "y"] Output: [] ```

Overview: Return every word in a list of distinct lowercase words that can be formed by joining two or more words from the same list, reusing words if needed, in input order. Tests splitting a string into dictionary words, fast set lookups, ordering work by word length, and efficiency on inputs with up to ten thousand words.

Read the full Amazon Software Engineer interview experience this question came from

Given a list of distinct lowercase words, return every word in the list that can be formed by joining two or more words from the same list end to end. A word `w` in the list is **compound** when `w` equals the concatenation `p1 + p2 + ... + pm` for some `m >= 2`, where every piece `pi` is a word in the list. The same word may be used as a piece more than once. Because there are at least two nonempty pieces, every piece is shorter than `w`, so a word never counts as a piece of itself. Implement `find_compound_words(words)`. Return the compound words in the order in which they appear in `words`. Return an empty list if there are none. ### Example 1 ```text Input: words = ["sun", "flower", "sunflower", "flowers", "s", "sunflowers", "pot"] Output: ["sunflower", "flowers", "sunflowers"] ``` `"sunflower"` is `"sun" + "flower"`, `"flowers"` is `"flower" + "s"`, and `"sunflowers"` is `"sun" + "flower" + "s"` (or `"sun" + "flowers"`). None of the other words can be split into words from the list. ### Example 2 ```text Input: words = ["ab", "abab", "aba", "b"] Output: ["abab"] ``` `"abab"` is `"ab" + "ab"`, using the same word twice. `"aba"` would need the remaining piece `"a"`, which is not in the list, and `"ab"` would need `"a" + "b"`. ### Constraints - `1 <= len(words) <= 10^4` - `1 <= len(words[i]) <= 30` - The total length of all the words is at most `10^5`. - Every word consists of lowercase English letters, and all words are distinct.

Constraints

  • 1 <= len(words) <= 10^4
  • 1 <= len(words[i]) <= 30
  • The total length of all the words is at most 10^5.
  • Every word consists of lowercase English letters, and all words are distinct.

Examples

Input: (['sun', 'flower', 'sunflower', 'flowers', 's', 'sunflowers', 'pot'],)

Expected Output: ['sunflower', 'flowers', 'sunflowers']

Explanation: Source example 1: sun+flower, flower+s and sun+flower+s (or sun+flowers); output keeps input order, not length order.

Input: (['ab', 'abab', 'aba', 'b'],)

Expected Output: ['abab']

Explanation: Source example 2: 'ab' is reused twice; 'aba' would need the missing piece 'a' (near miss).

Hints

  1. A word needs at least two pieces, so it can never be its own single piece; every piece is strictly shorter than the word being checked.
  2. The same listed word may be used as a piece more than once ("abab" is "ab" + "ab"), and a word with several valid splits, like "sunflowers", still appears in the answer only once.
  3. Every word in the list is available as a piece no matter where it appears, but the answer must follow the original order of words.

Loading coding console...

Show the approach

Approach

Put every word in a hash set. For each word w of length n, run a prefix dynamic program: can[0] is true, and can[i] is true when some j < i has can[j] true and w[j:i] is a listed word. The single split j = 0, i = n (the whole word as one piece) is excluded. A piece can never be longer than the longest word, so j only ranges over the last max_len positions before i.

Invariant: for i < n, can[i] is true exactly when the prefix w[0:i] is a concatenation of listed words; can[n] is true exactly when w is such a concatenation with at least two pieces. Because all words are distinct, a piece equal to w would have to be w itself, so excluding the whole-word split is exactly the m >= 2 rule; every split with m >= 2 uses only pieces shorter than w and is found because the program tries every split point, so it never misses a decomposition that taking the longest or shortest matching prefix first would skip. Set lookups do not consume words, so a piece may be reused any number of times.

Words are scanned in input order and appended at most once, which fixes the output order and lists a word with several decompositions only once. Which words are available as pieces does not depend on their position in the list. Edge cases: a one-letter word can never be compound (it would need two nonempty pieces), a singleton list returns [], and a list with no compounds returns [].

Time complexity:
O(S * K^2), where S <= 10^5 is the total length of all words and K <= 30 is the longest word length (up to K split starts per position, each hashing a piece of at most K characters)
Space complexity:
O(S) for the word set, plus O(K) per word for the split table