Concatenated Words

Photo by Tim Mossholder on Unsplash

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

Constraints:

• 1 <= words.length <= 104
• 1 <= words[i].length <= 30
• words[i] consists of only lowercase English letters.
• All the strings of words are unique.
• 1 <= sum(words[i].length) <= 105

Intuition

Check each word substrings are present in the words.

Approach

/*
 * step 1 - create a Hash using the words
 * step 2 - for each word in words check substrings are also present in words
 * Optimise 1 - get the minimum length of the word from the array, so we try finding the substring of min length at least always
 * Optimise 2 - have a visited set
 */

Complexity

• Time complexity:
  O(m.N2) — where m is the size of the words array and N² is to generating the substring
• Space complexity:
  O(m) — where m is the size of the words array

Code

public class Solution {
    public IList<string> FindAllConcatenatedWordsInADict(string[] words) {
        HashSet<string> set = new HashSet<string>();
        var visited = new HashSet<string>();
        var result = new List<string>();
        int min = int.MaxValue;

        foreach (var word in words){
        set.Add(word);
        min = Math.Min(min, word.Length);
        }

        foreach(string word in words) {
            if(Check(word)) result.Add(word);
        }
        
        bool Check(string word) {
            if (visited.Contains(word)) return true;
            for(int i = min; i <= word.Length - min; i++) {
                string left = word.Substring(0, i);
                string right = word.Substring(i);
                if(set.Contains(left)){
                    if(set.Contains(right) || Check(right)){
                        visited.Add(word);
                        return true;
                    }
                }
            }
    
        return false;
        }

        return result;
    }
}