4ms C++ DP Solution

  • 0

    class Solution {


    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
        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.