C++_DP_Accepted_9ms (Recursive Method: TLE)


  • 0

    // Credit to: https://discuss.leetcode.com/topic/7299/c-dynamic-programming-simple-and-fast-solution-4ms-with-optimization

    class Solution {
    public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(wordDict.empty()) return false;
        vector<bool> DP(s.size() + 1,false);
        DP[0] = true;
        for(int i = 1; i < DP.size(); i++){
            for(int j = i - 1; j >= 0; j--){
                if(DP[j]){
                    string t = s.substr(j, i - j);
                    if(wordDict.find(t) != wordDict.end()){DP[i] = true;break;}
                }
            }
        }
        return DP[s.size()];
    }
    };
    
    • TLE: Following is my original methods, I just want to use every s[i] as a cutting point to find out whether they could be found in the wordDict.
    • The DP methods is also very similar. Using the vector to store previous information, which DP[i] means that is DP[i] = true, then the string from s[0] to s[i-1] is available in the wordDict.
    • (That's also the reason why the length of DP is s.size() + 1 rather than s.size() )
    #code block
    
    //Time Limit Exceed
    class Solution {
    public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if(wordDict.empty()) return false;
        int n = s.size();
        if (wordDict.find(s) != wordDict.end()){return true;}
        bool res = true;
        for(int i = 1; i < n; i++){
            string s1 = s.substr(0,i);
            string s2 = s.substr(i);
            bool res1 = wordDict.find(s1) != wordDict.end();
            bool res2 = wordDict.find(s2) != wordDict.end();
            if(res1 && res2){ return true;}
            else if(!res1 && res2 && wordBreak(s1, wordDict)){return true;}
            else if(res1 && !res2 && wordBreak(s2, wordDict)){return true;}
            else if(wordBreak(s1, wordDict) && wordBreak(s2, wordDict)) {return true;}
        }
        return false;
    }
    };
    

    [alt text](0_1474667960549_upload-3577a289-4d73-412b-9e2c-d7c62fcf1403 image url)A69E2C7C-1416-4248-8C2D-EC11C20050BE.png


Log in to reply
 

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