4ms C++ dp solution (use length of strings in wordDict to segment string s)


  • 1
    N
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.length();
        if(len==0) return false;
        
        unordered_set<int> lenDict;
        for(string str:wordDict){
            lenDict.insert((int)str.length());
        }
        
        int dp[len+1] = {false}; //dp[i]: substring(0,i) can be segmented or not
        dp[0] = true;
        for(int i=0; i<=len; ++i){
            for(int j:lenDict){
                if(j<=i){
                    string tmp = s.substr(i-j,j); //substring length: j
                    if(wordDict.find(tmp) != wordDict.end()){
                        dp[i] = dp[i-j];
                        if(dp[i]) break;
                    }
                }
            }
        }
        return dp[len];
    }

Log in to reply
 

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