Concatenated Words with Minimal Segment Count
Given a list of unique words, words, find all words from this list that can be formed by concatenating two or more other words also present in words. Among all such concatenatable words, identify those that are formed using the minimum possible number of segments.
For example, if words = ["cat", "dog", "catdog", "catdogcat"]:
- "catdog" can be formed by "cat" + "dog" (2 segments).
- "catdogcat" can be formed by "catdog" + "cat" (2 segments) or "cat" + "dog" + "cat" (3 segments).
The minimum number of segments is 2. Both "catdog" and "catdogcat" can be formed using 2 segments. So, the output should be ["catdog", "catdogcat"] (the order of words in the output list does not matter).
If no words can be formed by concatenating two or more other words, return an empty list.
[ "cat", "dog", "catdog", "catdogcat" ]
[ "catdog", "catdogcat" ]
Explanation. "catdog" = "cat" + "dog" (2 segments). "catdogcat" = "catdog" + "cat" (2 segments, which is the minimum) or "cat" + "dog" + "cat" (3 segments). The overall minimum segment count is 2, and both "catdog" and "catdogcat" achieve it.
[ "apple", "pen", "pineapple", "applepen", "penapple", "applepenapple" ]
[ "applepen", "applepenapple", "penapple" ]
Explanation. "applepen" = "apple" + "pen" (2 segments). "penapple" = "pen" + "apple" (2 segments). "applepenapple" can be formed as "applepen" + "apple" (2 segments) or "apple" + "penapple" (2 segments) or "apple" + "pen" + "apple" (3 segments). The minimum segment count is 2 for all three words.
[ "a", "b", "c", "ab", "bc", "abc", "abcd" ]
[ "ab", "abc", "bc" ]
Explanation. "ab" = "a" + "b" (2 segments). "bc" = "b" + "c" (2 segments). "abc" = "ab" + "c" (2 segments) or "a" + "bc" (2 segments) or "a" + "b" + "c" (3 segments). The minimum segment count is 2 for all three. "abcd" cannot be formed by concatenating other words from the list.
[ "hello", "world", "coding", "helloworld" ]
[ "helloworld" ]
Explanation. "helloworld" = "hello" + "world" (2 segments). This is the only word that is concatenatable, and it uses 2 segments.
[ "a", "aa", "aaa" ]
[ "aa", "aaa" ]
Explanation. "aa" = "a" + "a" (2 segments). "aaa" = "a" + "aa" (2 segments) or "aa" + "a" (2 segments) or "a" + "a" + "a" (3 segments). Both "aa" and "aaa" can be formed with a minimum of 2 segments.
[ "a", "b", "c", "d", "e", "f", "ab", "abc", "def", "abcdef", "abcdefg" ]
[ "ab", "abc", "abcdef" ]
Explanation. "ab" = "a" + "b" (2 segments). "abc" = "ab" + "c" (2 segments). "def" = "d" + "e" + "f" (3 segments). "abcdef" = "abc" + "def" (2 segments, since "abc" and "def" are distinct words in the list) or "a" + "b" + "c" + "d" + "e" + "f" (6 segments). The minimum segment count is 2, achieved by "ab", "abc", and "abcdef". "def" is excluded as its minimum is 3 segments.
[]
[]
Explanation. An empty list of words contains no concatenatable words.
[ "word" ]
[]
Explanation. A single word cannot be formed by concatenating two or more *other* words from the list.
[ "apple", "banana", "orange" ]
[]
Explanation. None of these words can be formed by concatenating two or more other words from the list.
Follow-up: Can you extend your solution to handle cases where the dictionary of 'other words' is significantly larger than the list of 'target words' you need to check? How would your approach change if the problem also asked for the count of ways to form each word with the minimum segment count?
- The number of words in `words` will be between 0 and 10^4. - The length of each word will be between 1 and 30. - All words consist of lowercase English letters. - The input list `words` contains unique words.
- Views
- 14