8 ms C++ solution with explanation -- dp; no recursion


  • -1
    J

    This solution is a two-stage dynamic program. First: we use the solution from the Word Break problem to find all the break points -- the positions where we might possibly insert a space. The second dynamic program then builds up the actual solution by skipping through the break-points.

    Note: comments use python-like notation to indicate substrings. That is: s[:i] is the substring of s from position 0 up to, but not including, position j.

    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        int n = s.size();
        if (n == 0)
            return {};
            
        // First: identify the break points (and that there exists at least one way to break it).
        // D[i] = True if it is possible to break up s[:i] in at least one way.
        vector<bool> D(n+1, false);
        D[0] = true;
        for (int i=1; i <= n; i++) {
            for (int j=i-1; j >= 0 && D[i] == false; j--) {
                D[i] = D[j] && wordDict.find(s.substr(j, i-j)) != wordDict.end();
            }
        }
        
        if (!D[n])  // There is no solution.
            return {};
            
        // Find the i such that D[i] is true.
        // In given example: break_points = [0,3,4,7,10].
        vector<int> break_points;
        for (int i=0; i < D.size(); i++) {
            if (D[i]) {
                break_points.push_back(i);
            }
        }
        
        int m = break_points.size();
    
        // Now find the solution based on the breakpoints.
        // E[i]: Set of all strings we can create using s[:break_points[i]].
        // In the example: E[0] = [""], E[1] = ["cat"], E[2] = ["cats"], E[3] = ["cats and", cat sand"]
        vector<vector<string>> E(m); 
        E[0] = {""};
        for (int i = 0; i < m; i++) {
            for (int j=i-1; j >=0; j--) {  // Will now compute E
                // t is the string defined from breakpoints i to j
                string t = s.substr(break_points[j], break_points[i] - break_points[j]);  
                if (wordDict.find(t) != wordDict.end()) {
                    for (auto& u : E[j]) 
                        E[i].push_back(u + " " + t);
                }
            }
        }
        
        // Need to chop off the extra " " at the start of each string in E[m-1]
        vector<string> R;
        transform(E[m-1].begin(), E[m-1].end(), back_inserter(R), [](string& s) {return s.substr(1,s.size()-1);});
        return R;
    }

Log in to reply
 

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