C++_DP_very slow...but very easy to understand


  • 0

    OJ time: around 900ms....Shit.
    I will find a more efficient way to solve it..

    class Solution {
    public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        if(words.size() < 3) return {};
        unordered_set<string> st;
        for(auto word : words){st.insert(word);}
        vector<string> res;
        for(int i = 0; i < words.size(); ++i){
            if(find(st, words[i])){
                res.push_back(words[i]);
            }
        }
        return res;
    }
    
    bool find(unordered_set<string>& st, string s){
        vector<bool> dp(s.size()+1);
        dp[0] = true;
        int cnt = 0;
        st.erase(s);
        for(int i = 1; i < dp.size(); i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j]){
                    string tmp = s.substr(j,i-j);
                    if(st.find(tmp) != st.end()){
                        dp[i] = true;
                        cnt++;
                        break;
                    }
                }
            }
        }
        st.insert(s);
        return cnt >= 2 && dp[s.size()];//["a","b","ab","abc"]
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.