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 {
        bool wordBreak(string s, vector<string>& wordDict) {
            if(s.empty()) return false;
            unordered_set<string> dict;
            int maxLen = 0;
            for(auto it: wordDict){
                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;
            return chk[s.size()];

Log in to reply

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