ConcatenatedWords.java

package dynamic_programming;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by gouthamvidyapradhan on 12/06/2017.
 * Accepted
 * Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
 * <p>
 * A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
 * <p>
 * Example:
 * Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
 * <p>
 * Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
 * <p>
 * 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".
 * <p>
 * Note:
 * The number of elements of the given array will not exceed 10,000
 * The length sum of elements in the given array will not exceed 600,000.
 * All the input string will only include lower case letters.
 * The returned elements order does not matter.
 */
public class ConcatenatedWords {
    public static void main(String[] args) throws Exception {
        String[] words = {""};
        System.out.println(new ConcatenatedWords().findAllConcatenatedWordsInADict(words));
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> dictionary = new HashSet<>();
        for (String w : words)
            dictionary.add(w);
        List<String> result = new ArrayList<>();
        for (String w : words) {
            if (!w.isEmpty() && concatenatedWordsPossible(w, dictionary))
                result.add(w);
        }
        return result;
    }

    private boolean concatenatedWordsPossible(String word, Set<String> dictionary) {
        boolean[] D = new boolean[word.length() + 1];
        D[word.length()] = true;
        dictionary.remove(word); //remove current word from dictionary temporarily
        for (int i = word.length() - 1; i >= 0; i--) {
            for (int j = i, l = word.length(); j < l; j++) {
                String subStr = word.substring(i, j + 1);
                if (dictionary.contains(subStr) && D[j + 1]) {
                    D[i] = true;
                    break;
                }
            }
        }
        dictionary.add(word); //restore deleted word
        return D[0];
    }
}