6ms C++ Solution using memorization and backtracking


  • 0
    X
    class Solution {
    private:
        string join(vector<string> temp){
            reverse(temp.begin(), temp.end());
            string result = temp[0];
            for(int i=1; i<temp.size(); ++i)
                result = result + " " + temp[i];
            return result;
        }
        void findSol(vector<vector<int>> &pre_idxes, int cur_idx, vector<string> &result, vector<string> &temp, string &s){
            //in the given example;
            //dp is [false, false, true, true, false, false, true, false, false, true];
            //pre_idxes: {{}, {}, {0}, {0}, {}, {},{3, 4}, {}, {}, {7}
            if(cur_idx==-1){
                result.push_back(join(temp));
                return;
            }
            for(int idx : pre_idxes[cur_idx]){
                temp.push_back(s.substr(idx, cur_idx-idx+1));
                findSol(pre_idxes, idx-1, result, temp, s);
                temp.pop_back();
            }
        }
    public:
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> wordSet;
            int max_len = 0;
            //vector dp[i] is used to record the substring of s ending at index i could be broke as words;
            vector<bool> dp(s.length(), false);
            //vector pre_idxes[i] is used to record the indexes from where to i are words in the dict, if             //dp[i] is true, 
            vector<vector<int>> pre_idxes((int)s.length());
            for(string word : wordDict){
                wordSet.insert(word);
                max_len = max(max_len, (int)word.length());
            }
            
            for(int i=0; i<s.length(); ++i){
                for(int l=1; l<=max_len && i-l+1>=0; ++l){
                    if((i-l < 0 || dp[i-l]) && wordSet.count(s.substr(i-l+1, l))){
                        dp[i] = true;
                        pre_idxes[i].push_back(i-l+1);
                    }
                }
            }
            vector<string> result;
            vector<string> temp;
            //then find the solution backwards using backtracking;
            findSol(pre_idxes, (int)s.length()-1, result, temp, s);
            return result;
        }
    };
    

Log in to reply
 

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