[数据结构与算法]Leetcode 472. Concatenated Words

题目

解法：

利用word break解法即可
注意：

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

class Solution {
public:
    bool canBreak(string s,unordered_map<string,bool> &d){
        vector<bool> dp(s.size()+1,false);
        dp[0] = true;
        for(int i=0;i<s.size();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<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_map<string,bool> d;
        for(auto& word : words){
            d[word] = true;
        }
        vector<string> 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的平均长度

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖