4ms C++ DP Solution


  • 0
    S

    class Solution {

    public:

    bool wordBreak(string s, unordered_set<string>& wordDict) {
        if (s.empty()) return false;
        int minLength = INT_MAX;
        int maxLength = 0;
    
         // get the min/max length to limit the search space.   
        for(auto str:wordDict)
        {
            minLength = min(minLength, (int)str.size() );
            maxLength = max(maxLength, (int)str.size() );
        }
        vector<bool> buffer(s.size(), false);
        for(int i=0; i<s.size(); i++)
        {
            for(int j = minLength; j<=maxLength && (i+j)<=s.size(); j++)
                if (!buffer[i+j-1])    //if index"i_j-1" cannot be researchable, we need to check if we can
                    if (wordDict.find(s.substr(i, j)) != wordDict.end())
                        buffer[i+j-1] = true;
            while(buffer[i] == false && i<s.size())   //go to the next breaking point
                i++;
        }
        return buffer[s.size()-1];
    }
    

    };


Log in to reply
 

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