Frontend School

Find Concatenable Words

DSA
medium

Find Concatenable Words

Medium
String
Trie
Dynamic Programming

Overview

Imagine you're building a sophisticated text processing engine for a dictionary service. A common challenge is identifying words that are themselves composed of other, simpler words. For instance, "catdog" is formed by "cat" and "dog". Your task is to implement a feature that finds all such "concatenable" words from a given list.

What you need to do / Task

Given an array of strings words, return a list of all concatenable words in the given words list. A concatenable word is a word that can be formed by concatenating at least two other words from the given words list.

Input & output

Input:

  • words: An array of strings, where each string is a word composed of lowercase English letters.

Output:

  • An array of strings, containing all concatenable words found in the input words list. The order of words in the output list does not matter.

Clarifications

  • A word is considered "concatenable" if it can be formed by combining two or more distinct words from the original input list. For example, if "cat" and "dog" are in the list, then "catdog" is concatenable.
  • The component words must be from the same input list.
  • A word cannot be formed by itself. For example, "cat" cannot be considered concatenable just because "cat" is in the list (it would only be one segment). It needs at least two segments.

Examples

1

Example 1

Input:

words = ["cat","dog","catdog"]

Output:

["catdog"]

Note:

"catdog" can be formed by concatenating "cat" and "dog", both of which are present in the input list. "cat" and "dog" themselves are not concatenable as they are single words.

2

Example 2

Input:

words = ["apple","pie","applepie","ap","ple","applep","ie"]

Output:

["applepie"]

Note:

"applepie" can be formed by "apple" + "pie" or "ap" + "ple" + "pie" or "applep" + "ie". All component words exist in the input list. The minimum segments would be 2 (e.g., "apple" + "pie").

3

Example 3

Input:

words = ["a","b","ab","abc","c"]

Output:

["ab"]

Note:

"ab" can be formed by "a" + "b". "abc" is not concatenable in this list because its components ("c", "bc", "abc") are not all present in the list in a way that forms at least two distinct segments. The words "a", "b", "c" are not concatenable by themselves.

Constraints

Constraints & assumptions

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 30
  • words[i] consists of lowercase English letters.
  • All words[i] are unique.
  • The order of words in the output list does not matter.

What interviewers evaluate

  • Correctness: Does the solution correctly identify all concatenable words based on the problem definition and constraints?
  • Efficiency: Is the solution's time and space complexity optimal for the given constraints? Consider the use of appropriate data structures and algorithms.
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand? Does it handle edge cases gracefully?
  • Algorithm Design: Does the candidate demonstrate a clear understanding of the problem and choose an appropriate algorithmic approach (e.g., Trie, Dynamic Programming)?

Loading editor...