Leetcode 472. Concatenated Words

利用word break解法即可
注意：

1. c++在写的时候，这个参数一定要传引用，不然会占据很大的时间，比如下面的unordered_map &d，如果不传引用会tle
2. 像这边的d可以直接用unordered_set, unordered_set s(words.begin(), words.end());

class Solution {
public:
    bool canBreak(string s,unordered_map &d){
        vector dp(s.size()+1,false);
        dp[0] = true;
        for(int i=0;i
            for(int j=i;j>=0;j--){
                if(dp[j] && d.find(s.substr(j,i-j+1)) != d.end()){
                    dp[i+1] = true;
                }
            }
        }
        return dp.back();
    }
    vector findAllConcatenatedWordsInADict(vector& words) {
        unordered_map d;
        for(auto& word : words){
            d[word] = true;
        }
        vector ans;
        for(auto& word : words){
            if(word == "") continue;
            d.erase(word);
            if(canBreak(word,d)){
                ans.push_back(word);
            }
            d[word] = true;
        }
        // cout << canBreak("catsdogcats",d) << endl;
        return ans;
    }
};

时间复杂度：O(m*n^2),m为words长度，n为所有word的平均长度