package com.company;

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

public class Main {

    static class Node {
        public char c;
        public Map<Character, Node> next = new HashMap<>();
        public boolean leaf = false;

        public Node(char c) {
            this.c = c;
        }
    }

    static Node build(String[] words) {
        Node node = new Node('-');
        for (String word : words) {
            Node currentNode = node;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                currentNode.next.putIfAbsent(c, new Node(c));
                currentNode = currentNode.next.get(c);
            }
            currentNode.leaf = true;
        }
        return node;
    }

    public static List<String> findAllConcatenatedWordsInADict(String[] words) {
        Node node = build(words);
//        dfs(node, "");
        Set<String> ans = new HashSet<>();
        for (String word : words) {
            dfs(word, node, node, 0, 0, ans);
        }
        return new ArrayList<>(ans);
    }

    static void dfs(String currentWord, Node currentNode, Node root, int pos, int cnt, Set<String> ans) {
        if (pos > currentWord.length() - 1) {
            if (cnt > 1) {
                ans.add(currentWord);
            }
            return;
        }
        char currentChar = currentWord.charAt(pos);
        if (currentNode.next.containsKey(currentChar)) {
            Node nextNode = currentNode.next.get(currentChar);
            dfs(currentWord, nextNode, root, pos + 1, cnt, ans);
            if (nextNode.leaf) {
                dfs(currentWord, root, root, pos + 1, cnt + 1, ans);
            }
        }
    }

    static void dfs(Node node, String word) {
        if (node.leaf) {
            System.out.println(word + node.c);
        }
        node.next.values().forEach(d -> dfs(d, word + node.c));
    }

    public static void main(String[] args) {
        String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
        List<String> allConcatenatedWordsInADict = findAllConcatenatedWordsInADict(words);
        for (String s : allConcatenatedWordsInADict) {
            System.out.println(s);
        }

    }
}