Concatenated Words

This page explains Java solution to problem Concatenated Words using Dynamic Programming algorithm.

Problem Statement

Given a list of words (without duplicates), please write a program that returns all 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.

Input: ["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"

Solution

package com.vc.hard;

import java.util.*;

class ConcatenatedWords {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, new Comparator<String>(){
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(), s2.length());
            }
        });

        HashSet<String> set = new HashSet<>();
        List<String> res = new ArrayList<>();
        for(String word: words) {
            if(canForm(word, set)) res.add(word);
            set.add(word);
        }
        return res;
    }

    private boolean canForm(String word, HashSet<String> set) {
        if(set.isEmpty()) return false;
        int n = word.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for(int i = 1; i <= word.length(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && set.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

Time Complexity

O(N * K²) Where
N is total number of elements in an input string array words
K is length of longest word in an input array

Space Complexity

O(N) Where
N is total number of elements in an input string array words