Accepted concise C++ solution 60ms


  • 0
    K

    Straightforward solution which is adapted from the previous question, disregarding the space cost.

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            int n = s.length();
            // allocate dp array which saves all breaking combinations of sub-string i to the end
            vector<string> res[n+1];
            if(n ==0) return res[0];
            if(dict.size() ==0) return res[0];
            res[n].push_back("");
            // backward pointer matching sub-string from i to j
            for(int i=n-1;i>=0;i--){
                vector<string> newa;
                for(int j=i;j<n;j++){
                    string txt= s.substr(i,j-i+1);
                    vector<string> a(res[j+1]);
                    // complete the string from i to the end by concatenating 
                    // the sub-string of i to j and the sub-strings of j+1 to the end
                    if(dict.find(txt) != dict.end()){
                        for(int k=0;k<a.size();k++){
                            string newtxt= a[k].empty()?txt:txt + " " + a[k];
                            newa.push_back(newtxt);
                        }
                    }
                }
                res[i] = newa;
            }
            return res[0];
        }
    };

Log in to reply
 

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