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

  • 1
    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){
        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){
                    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.