Find Concatenable Words
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.
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:
words: An array of strings, where each string is a word composed of lowercase English letters.Output:
words list. The order of words in the output list does not matter.Examples
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.
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").
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
1 <= words.length <= 10^41 <= words[i].length <= 30words[i] consists of lowercase English letters.words[i] are unique.Loading editor...