c++ 3ms Iterative


  • 0
    G
    class Solution {
        vector<int> dp;
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            if(s.empty()) return true;
            if (dp.empty()) dp.resize(s.size()+1, -1); // -1: not computed before
            
            for (int i = 0; i < wordDict.size(); i++){
                
                int l = wordDict[i].size();
                if (l > s.size()) continue;
                
                if (s.substr(0,l) == wordDict[i]){
                    if (dp[l] == -1) { // if not computed before, compute it
                        bool tmp = wordBreak(s.substr(l), wordDict);
                        if (tmp) return true; // if true, return immediately
                        dp[l] = 0; // means "computed, but false"
                    }
                }
            }
            
            return false;
        }
    };
    

Log in to reply
 

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