[DP] Clean C++ 3ms recursion with comments


  • 0
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_map<string,int>m;
            unordered_map<string,bool>dp; //Store the sub-result.
            int maxlen=0;  //Store the length of longest word for optimization.
            for(auto x:wordDict){
                m[x]++;
                if(x.size()>maxlen) maxlen=x.size();
            }
            return find(s,m,maxlen,dp);
        }
        
        bool find(string s, unordered_map<string,int>& m,int maxlen,unordered_map<string,bool>& dp){
            if(s.size()==0||m[s]>0) return true;
            if(dp.count(s)>0) return dp[s];
            bool b=false;
            for(int i=1;i<s.size()+1;i++){
                if(m[s.substr(0,i)]>0) b|=find(s.substr(i),m,maxlen,dp);
                if(b||i>maxlen) break; //if we find a 'combo' or length of substring is longer than maxlen, we stop searching.
            }
            dp[s]=b;
            return b;
        }
    

Log in to reply
 

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