C++ 4ms DP solution (with comments)


  • 1
    G
    class Solution {
        // (optimization) the longest word length in dictionary
    	int longestLen;
    	// DP: store string results that have already solved
    	unordered_map<string, bool> stored;
    
    public:
    	Solution() :longestLen(-1) {}
    
    	bool wordBreak(string s, unordered_set<string>& wordDict) {
    	    // check if s has been solved already
    		auto ret = stored.find(s);
    		if (ret != stored.end()) {
    		    // return stored result
    			return ret->second;
    		}
    		
    		// get the the longest word length in dictionary
    		if (longestLen == -1) {
    			for (auto word : wordDict) {
    				if ((int)word.length() > longestLen) {
    					longestLen = word.length();
    				}
    			}
    		}
    
            // only get substring that <= longestLen
    		for (int len = 1, i = 0; len <= longestLen && i < s.length(); len++) {
    			string sub = s.substr(i, len);
    			// check if substring is in the dictionary
    			if (wordDict.find(sub) != wordDict.end()) {
    			    // in dict && reach the end, store and return true
    				if (i + len == s.length()) {
    					stored[s] = true;
    					return true;
    				}
    				// recursive check substring (only return when true obtained)
    				if (wordBreak(s.substr(len), wordDict)) {
    					stored[s] = true;
    					return true;
    				}
    			}
    		}
    		
    		// no found
    		stored[s] = false;
    		return false;
    	}
    };
    

    I first obtain the longest word length in dictionary as the upper boundary of the loop for optimization purpose. Loop to test sub-string with length in [1, longestLen]. Once found the match sub-string s[i, j], store the result for s and recursively check s[j+1, s.length()-1].


Log in to reply
 

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