Evolve from brute force


  • 1
    1. O(2^n)
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> res;
            string one;
            wordBreak(0,one,s,wordDict,res);
            return res;
        }
        void wordBreak(int p, string &pre, string& s, unordered_set<string>& wordDict,vector<string>& res) {
            int n = s.size();
            if(p==n) {
                pre.pop_back();
                res.push_back(pre);
            }
            string cur;
            int sz = pre.size();
            for(int i=p;i<n;i++) 
                if(wordDict.count(cur+=s[i])) {
                    pre+=cur;
                    pre+=' ';
                    wordBreak(i+1, pre,s,wordDict,res);
                    pre.resize(sz);
                }
        }
    
    1. Memorization. Break each substr only once and cache the results.
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<int,vector<string>> mem({{s.size(),vector<string>()}});
            wordBreak(0,s,wordDict,mem);
            return mem[0];
        }
        void wordBreak(int p, string& s, unordered_set<string>& wordDict, unordered_map<int,vector<string>>& mem) {
            if(mem.count(p)) return;
            string cur;
            mem[p];
            int n = s.size();
            for(int i=p;i<n;i++) {
                if(!wordDict.count(cur+=s[i])) continue;
                wordBreak(i+1, s,wordDict,mem);
                if(i==n-1) {
                    mem[p].push_back(cur);
                    continue;
                }
                vector<string> &v = mem[i+1];
                for(string s:v) mem[p].push_back(cur+' '+s);
            }
        }
    
    1. Another way to improve #1 is pre-computing the break points and then search from the break points only.
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            int n=s.size();
            vector<bool> canBrk(n+1,false);
            canBrk[n]=true;
            for(int i=n-1;i>=0;i--) {
                string ss;
                for(int j=i;j<n;j++) {
                    ss+=s[j];
                    if(!wordDict.count(ss)||!canBrk[j+1]) continue;
                    canBrk[i]=true;
                    break;
                }
            }
            vector<string> res;
            string one;
            recur(0,one,s,canBrk,wordDict, res);
            return res;
        }
        void recur(int id,string &cur,string &s,vector<bool>& canBrk, unordered_set<string>& wordDict,vector<string> &res) {
            if(!canBrk[id]) return;
            int n=s.size();
            if(id==n) {
                cur.pop_back();
                res.push_back(cur);
                return;
            }
            int cs=cur.size();
            string ss;
            for(int i=id;i<n;i++) {
                ss+=s[i];
                cur+=s[i];
                if(!wordDict.count(ss)) continue;
                cur+=' ';
                recur(i+1,cur,s,canBrk,wordDict,res);
                cur.pop_back();
            }  
            cur.erase(cs);
        }
    

Log in to reply
 

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