Concatenated Words_dp.cpp

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        int len = words.size();
        auto comp = [](const string& lhs, const string& rhs){return lhs.size() < rhs.size();};
        sort(words.begin(), words.end(), comp);
        unordered_set<string> dict;
        vector<string> res;
        for(auto&& word : words)
        {
            if(canBreak(word, dict)){res.push_back(word);};
            dict.insert(word);
        }
        return res;
    }
    
private:
    bool canBreak(string& str, unordered_set<string>& dict)
    {
        if(dict.empty())return false;
        int len = str.size();
        vector<bool> dp(len + 1, false);
        dp[0] = true;
        for(int i = 0; i < len; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                if(dp[j] && dict.find(str.substr(j, i - j + 1)) != dict.end())
                {
                    dp[i + 1] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};