Leetcode Concatenated Words problem solution

by

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;
    }
};