concise 6ms C++ solution with DP


  • 1
    R
    void buildResult(vector<string>& res, vector<vector<int>>& dp, string& s, int i, string& path) {
        if(i < 0) {
            res.push_back(path);
            res.back().pop_back();
            reverse(res.back().begin(), res.back().end());
            return;
        }
        for(int len : dp[i+1]) {
            for(int j=0; j<len; j++) path.push_back(s[i-j]); path.push_back(' ');
            buildResult(res, dp, s, i-len, path);
            for(int j=0; j<=len; j++) path.pop_back();
        }
    }
    
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        int maxLen = 0;
        for(auto& w : wordDict) maxLen = max(maxLen, (int) w.size()); 
        vector<vector<int>> dp(1+s.size(), vector<int>());
        dp[0].push_back(0);
        for(int i=0; i<s.size(); i++) {
            for(int len = 1; len <= maxLen && i-len+1 >= 0; len++) {
                string word = s.substr(i-len+1, len);
                if(wordDict.find(word) != wordDict.end() && dp[1+i-len].size() > 0) {
                    dp[1+i].push_back(len); // store valid word lengths
                }
            }
        }
        
        // build result with backtracking
        vector<string> res;
        string path;
        buildResult(res, dp, s, s.size()-1, path);
        return res;
    }
    

  • 1
    A

    i think this solution is more better than memorize the whole path.


Log in to reply
 

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