Shared my very clean AC C++ code


  • 0
    R
    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            map<string, vector<string>> cache;
            return wordBreak(s, wordDict, cache);
        }
    private:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict,
                                map<string, vector<string>>& cache) {
            if(cache.count(s))  return cache[s];
            vector<string> result;
            for(int i=0; i<s.size(); ++i) {
                string s1=s.substr(0, i+1);
                string s2=s.substr(i+1, (int)s.size()-(i+1)+1);
                if(wordDict.count(s1)){
                    if(s2.size()==0){
                        result.push_back(s1);
                    }else{
                        vector<string> right=wordBreak(s2, wordDict, cache);
                        if(right.size()!=0)
                            combine(s1, right, result);    
                    }
                }
            }
            return cache[s]=result;
        }
    private:
        void combine(string& left, vector<string>& right, vector<string>& result) {
            for(int i=0; i<right.size(); ++i){
                string temp=left+" "+right[i];
                result.push_back(temp);
            }
        }
    };

  • 0
    X

    one quick and small thing:
    s.substr(i+1, (int)s.size()-(i+1)+1) = s.substr(i+1)


Log in to reply
 

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