1221. Concatenated Words

Code(Language:C++)

class Solution {
public:
    /**
     * @param words: List[str]
     * @return: return List[str]
     */
    vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
        // write your code here
        unordered_set<string> hset; 
        int maxLen = 0;
        int minLen = INT_MAX;
        /*for(auto i : words){
            hset.insert(i);
            int tmp = i.size(); 
            minLen = min(minLen, tmp);
            maxLen = max(maxLen, tmp); 
        }
        */
        hset.insert(words.begin(), words.end()); 
        vector<string> res; 
        for(auto word : words){
            /*if(word.size() == minLen){
                continue; 
            }
            */
            int n = word.size();
            vector<bool> dp(n + 1);
            dp[0] = true; 
            for (int i = 0; i < n; ++i) {
                    if (dp[i] == 0) {           // cannot start from here
                        continue;
                    }
                    for (int j = i + 1; j <= n; ++j) {      // check whether w.substr(i, j - i) can be concatenated from i
                        if (j - i < n && hset.count(word.substr(i, j - i))) {// cannot be itself
                            dp[j] = true;
                        }
                    }
                    if (dp[n]) {
                        res.push_back(word); 
                        break; 
                    }
                }
        }
        return res; 
    }
};