In this Leetcode  Concatenated Words problem solution 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.

Leetcode  Concatenated Words problem solution


Problem solution in Python.

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        self.dic = set(words)
        return [word for word in words if self.DFS(word, {})]
    
    def DFS(self, word, memo) -> bool:
        if word in memo: return memo[word]
        
        memo[word] = False
        for i in range(1, len(word)):
            prefix = word[:i]
            suffix = word[i:]
            
            if prefix in self.dic and suffix in self.dic: 
                memo[word] = True
                break
            if prefix in self.dic and self.DFS(suffix, memo):
                memo[word] = True
                break
        return memo[word]

Problem solution in Java.

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort (words, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                return s1.length() - s2.length();
            }
        });
        List<String> finAns = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            if (present (words[i], preWords))
                finAns.add (words[i]);
            preWords.add(words[i]);
        }
        return finAns;
    }
    
    public boolean present (String word, Set<String> preWords) {
        if (preWords.isEmpty()) return false;
        boolean[] dp = new boolean[word.length()+1];
        dp[0] = true;
        for (int i = 1; i <= word.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (!dp[j]) continue;
                if (preWords.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.length()];
    }
}

Problem solution in C++.

struct trie{
    trie* ptr[26];
    bool isword;
    trie(){
        for(int i=0;i<26;i++)ptr[i] = NULL;
        isword = false;
    }
};

typedef trie* tptr;
void insert(tptr t,string s){
    for(int i=0;i<s.length();i++){
        if(!t->ptr[s[i]-'a'])t->ptr[s[i]-'a'] = new trie();
        t = t->ptr[s[i]-'a'];
    }
    t->isword = true;
}
bool morethan2(tptr root,string s,int i=0,int cnt=1){
    tptr t = root;
    for(int j=i;j<s.length();j++){
        if(!t->ptr[s[j]-'a'])return false;
        t = t->ptr[s[j]-'a'];
        if(t->isword && morethan2(root,s,j+1,cnt+1))return true;
    }
    return (t->isword && cnt>1);
}

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        tptr t = new trie();
        int n = words.size();
        for(string s : words)if(!s.empty())insert(t,s);
        vector<string>ans;
        for(string s : words){
            if(morethan2(t,s))ans.emplace_back(s);
        }
        
        return ans;
    }
};