Accepted C++ DP code in 3ms


  • 0

    The DP idea is very similar to the other C++ code.
    However, I use the maximum length of word inside the dictionary to speed up the process.
    This code wins over 90.75% of others.

    class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            if(s.empty()) return false;
            unordered_set<string> dict;
            int maxLen = 0;
            for(auto it: wordDict){
                dict.insert(it);
                maxLen = max((int)it.size(), maxLen);
            }
            
            vector<bool> chk(s.size()+1, false);
            chk[0] = true;
            for(int i=1 ; i<=s.size() ; i++){
                for(int j=max(0,i-maxLen) ; j < i ; j++){
                    string tmp = s.substr(j,i-j);
                    if(chk[j] && dict.find(tmp)!=dict.end()){
                        chk[i] = true;
                        break;
                    }
                }
            }
            return chk[s.size()];
        }
    };
    

Log in to reply
 

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