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.

&nbsp;
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"]


&nbsp;
Constraints:


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


class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
                
        set_words = set(words)

        def check(word, seen):
            if word == '':
                return True
            for i in range(len(word) if seen else len(word) - 1):
                if word[:i+1] in set_words:
                    if check(word[i+1:], seen | {word[:i+1]}):
                        return True
            return False

        return [word for word in words if check(word, set())]
class Solution {
	Set<String> set = new HashSet<>();
	Set<String> res = new HashSet<>();
	int index = 0;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        for (String word: words) set.add(word);
		for (String word: words) {
	        int len = word.length();
	        index = 0;
	        backtrack(len, word, 0);
        }
        List<String> list = new ArrayList<>();
        for (String word: res) list.add(word);
        return list;
    }
	public void backtrack (int len, String word, int num) {
	    if (index == len && num >= 2) {
            res.add(word);
        }
	    int indexCopy = index;
	    for (int i = index + 1; i <= len; i++) {
		    if (set.contains(word.substring(index, i))) {
	            index = i;
	            backtrack(len, word, num + 1);
	            index = indexCopy;
            } 
        }
        return;
    }
}
class Solution {
public:
    int checkForConcatenation( unordered_set<string>& st, string w, int i, vector<int>& dp){
        if(i == w.size()) return 1;
        if(dp[i] != -1) return dp[i];
        for(int j = i; j < w.size(); ++j ){
            string t = w.substr(i, j-i+1);
            if(t.size() != w.size() && st.find(t) != st.end()){
                if(checkForConcatenation(st, w, j+1, dp)) return dp[i] = 1;
            }
        }
        return dp[i] = 0;
    }
    
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> ans;
        unordered_set<string> st;
        for(auto w: words) st.insert(w);
        for(auto w: words){
            vector<int> dp(w.size(), -1);
            if(checkForConcatenation(st, w, 0, dp)) ans.push_back(w);
        }
        return ans;
    }
};
class Node {
    val;
    children;
    isWord = false;
    constructor(val) {
        this.val = val;
    }

}
class Trie {
    nodes = Array(26);
    addWord(w) {
        let idx = this.getIdx(w[0]);
        let node = this.nodes[idx] || new Node(w[0]);
        this.nodes[idx] = node;
        for (let i=1; i < w.length; ++i) {
            node.children = node.children || Array(26);
            idx = this.getIdx(w[i]);
            let childNode = node.children[idx] || new Node(w[i]);
            node.children[idx] = childNode;
            node = childNode;
        }

        node.isWord = true;
    }

    getExistingWords(w, start) {
        const rslt = [];
        let node = {children: this.nodes};
        for (let i=start; i < w.length; ++i) {
            node = (node.children || [])[this.getIdx(w[i])];
            if (!node) {
                break;
            }

            if (node.isWord) {
                rslt.push(i-start+1);
            }
        }

        return rslt;
    }

    getIdx(ch) {
        return ch.charCodeAt(0) - "a".charCodeAt(0);
    }
}

var findAllConcatenatedWordsInADict = function(words) {
    const rslt = [];
    words = words.sort((a,b) => a.length-b.length);
    let start = 0;
    if (words[0].length === 0) {
        ++start;
    }
    const tr = new Trie();
    for (let i = start; i < words.length; ++i) {
        if (check(words[i], 0, tr, Array(words[i].length))) {
            rslt.push(words[i]);
        }
        tr.addWord(words[i]);
    }

    return rslt;
};

function check(word, i, trie, dp) {
    if (i > word.length || dp[i] === false) {
        return false;
    }
    if (i === word.length || dp[i] === true) {
        return true;
    }
    const lens = trie.getExistingWords(word, i);
    if (!lens.length) {
        dp[i] = false;
        return false;
    }

    dp[i] = true;
    for (let l of lens) {
        if (check(word, i+l, trie, dp)) {
            return true;
        }
    }

    dp[i] = false;

    return false;
}
Concatenated Words