Quick Overview

This question evaluates proficiency in string manipulation, efficient lookup structures (e.g., hashing/trie) and dynamic programming or recursion for word segmentation, testing algorithmic efficiency and data-structure selection within the Coding & Algorithms domain.

Find concatenated words in list

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question LeetCode 472. Concatenated Words – Given an array of strings words, return all words that are concatenations of at least two shorter words also present in the array. leetcode.com/problems/concatenated-words/description/

Quick Answer: This question evaluates proficiency in string manipulation, efficient lookup structures (e.g., hashing/trie) and dynamic programming or recursion for word segmentation, testing algorithmic efficiency and data-structure selection within the Coding & Algorithms domain.

Given an array of strings `words` (without duplicates), return all the words that are *concatenated words* in the given list. A **concatenated word** is defined as a string that is composed entirely of at least two shorter words (not necessarily distinct) from the same input array. **Example 1:** ``` Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" = "cats" + "dog" + "cats" "dogcatsdog" = "dog" + "cats" + "dog" "ratcatdogcat"= "rat" + "cat" + "dog" + "cat" ``` **Example 2:** ``` Input: words = ["cat","dog","catdog"] Output: ["catdog"] ``` Return the concatenated words in any order. The empty string is never a concatenated word.

Constraints

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 30 (per LeetCode); the input contains no duplicate words
  • words[i] consists of lowercase English letters
  • 0 <= sum of words[i].length <= 10^5
  • A concatenated word must be formed from at least two shorter words already present in the array
  • Component words may be repeated (e.g. "cats"+"dog"+"cats")

Examples

Input: (["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"],)

Expected Output: ['catsdogcats', 'dogcatsdog', 'ratcatdogcat']

Explanation: Canonical example: 'catsdogcats'=cats+dog+cats, 'dogcatsdog'=dog+cats+dog, 'ratcatdogcat'=rat+cat+dog+cat. 'hippopotamuses' cannot be split into other listed words.

Input: (["cat","dog","catdog"],)

Expected Output: ['catdog']

Explanation: 'catdog' = 'cat' + 'dog', a concatenation of exactly two shorter words.

Hints

  1. A word qualifies if it can be broken ("word-broken") into pieces that are all themselves in the dictionary — this is the classic Word Break problem applied to each word.
  2. Put all words in a hash set for O(1) average lookups, then run a DP over each word: dp[i] is true if the prefix of length i can be segmented into dictionary words.
  3. To enforce 'at least two shorter words', forbid using the whole word itself as a single piece — exclude the segment that spans the entire word (j==0 and i==len).
  4. Be careful with the empty string: it should never be reported, and don't let it act as a free zero-length building block.

Loading coding console...