Trie with Explanations
\nA concatenated word is a word add other word(words) as prefix.\n\nWe have to answer a question recursively: is a substring(word[x, word.length()-1]) prefixed 
```\nA concatenated word is a word add other word(words) as prefix.\n\nWe have to answer a question recursively: is a substring(word[x, word.length()-1]) prefixed with another word in words?\n\nThat\'s natural to prefix tree(trie). \n\nWe can build a trie using words and search for concatenated words in the trie. \n\nWe have to make a decision when we meet a node that meets the end of a word (with en in the example below). We can\n  - either take the current node\'s associated word as prefix (and restart at root for another word) \n  - or not take the current node\'s associated word as prefix (i.e. move further within the same branch).\nFor example,\n    root           \n     /\\\n    c  d\n    /   \\\n    a    o\n   /      \\\n  t(en)    g(en)\n  /         \n s(en)    \n \nTo concatenate catsdogcats using {cat, cats, dog}\nsearch tree: (-\'s in the same vertical line are sibling nodes)\n    root - c - a - t(en)  - X [to take cat as prefix doesn\'t work]\n                          - s(en) - d - o - g(en) - c - a - t  - s(en) DONE!\n                                                  - X [not to take dog as prefix doesn\'t work]\n                                  -  [not to take cats as prefix doesn\'t work]\n```\n****\n```\nclass Solution {\n    private static Node root;\n    \n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        if (words == null || words.length == 0)\n            return new ArrayList<>();\n        \n        root = new Node();\n        buildTrie(words);\n        \n        List<String> result = new LinkedList<>();\n        for (String word : words) {\n            if (isConcatenated(word, 0, 0))\n                result.add(word);\n        }\n        return result;\n    }\n    \n    // Return true if word starting from index is concatenated\n    boolean isConcatenated(String word, int index, int countConcatenatedWords) {\n        if (index == word.length())\n            return countConcatenatedWords >= 2;\n        \n        Node ptr = root;\n        for (int i = index; i < word.length(); i++) {\n            if (ptr.children[word.charAt(i) - \'a\'] == null) \n                return false;\n            ptr = ptr.children[word.charAt(i) - \'a\'];\n            \n            if (ptr.isWordEnd)\n                if (isConcatenated(word, i + 1, countConcatenatedWords + 1))\n                    return true;\n        }\n        \n        return false;\n    }\n    \n    private void buildTrie(String[] words) {\n        Node ptr;\n        for (String word : words) {\n            ptr = root;\n            for (char ch : word.toCharArray()) {\n                int order = ch - \'a\';\n                if (ptr.children[order] == null) {\n                    ptr.children[order] = new Node();\n                } \n                ptr = ptr.children[order];\n            }\n            ptr.isWordEnd = true;\n        }\n    }\n    \n    class Node {\n        Node[] children;\n        boolean isWordEnd;\n        \n        public Node() {\n            children = new Node[26];\n            isWordEnd = false;\n        }\n    }\n}\n```\n
[]