CPP DP solution, 3ms beats 81%


  • 0
    K

    DP solution, clear comment

    class Solution {
    public:
      //helper function to sort
        bool static comp(string &a,string &b){
            return a.length()<b.length();
        }
        bool wordBreak(string s, vector<string>& wordDict) {
            //description said nonempty,it's a lie 
            if(s.length()==0||wordDict.size()==0)
                return false;
    
            int slen = s.length();
            vector<string> tv;
            //if found any wordDict item in string,save it
            for(auto i:wordDict){
                if(s.find(i)!=string::npos){
                    tv.push_back(i);
                }
            }
            //be sure this vector is nonempty
            if(tv.size()==0)
                return false;
    
            //sort by length of item
            sort(tv.begin(),tv.end(),comp);
            //dp[i] means can items in wordDict make up s.substr(0,i)
            vector<bool> dp(slen+1,false);
            dp[0] = true;
            //the sorted vector tv,tv[0] is the least length
            for(int i = tv[0].length();i<=slen;i++){
                for(auto str:tv){
                    int l = str.length();
                    //length of str may be larger than i,skip it
                    if(i>=l){
                        //s.substr(0,i) = s.substr(0,i-l)+s.substr(i-1,l)
                        //so we just need to know whether these two parts are both true
                        dp[i]=dp[i-l]&&(s.substr(i-l,l)==str);
                        //once true,save it and break
                        if(dp[i])
                            break;
                    }
                }
            }
            return dp[slen];
        }
    };
    

Log in to reply
 

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