Accepted concise C++ solution 60ms

  • 0

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

    class Solution {
        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];
            // 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];
                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.