C++: clear implementation with back tracking, easy to understand


  • 0
    W
    class Solution {
        
    void helper(string s, unordered_set<string> wordDict, vector<string>& temp, vector<string>& res, int ind){
        if (ind == s.size()){
            string temp_string;
            int i;
            for (i = 0; i < temp.size() - 1; ++i){
                temp_string = temp_string + temp[i] + " ";
            }
            temp_string = temp_string + temp[i];
            res.push_back(temp_string);
        }else {
            for (int i = ind; i < s.size(); ++i){
                string sub = s.substr(ind, i - ind + 1);
                if (wordDict.find(sub) != wordDict.end()){
                    temp.push_back(sub);
                    helper(s, wordDict, temp, res, i + 1);
                    temp.pop_back();
                }
            }
        }
    }
    
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> res;
            int n = s.size();
            vector<bool> f(n + 1, false);
            f[0] = true;
            for (int i = 0; i < n; ++i){
                for (int j = i; j >= 0 ; --j){
                    string sub = s.substr(j, i - j + 1);
                    if (wordDict.find(sub) != wordDict.end()){
                        f[i + 1] = f[j];
                    }
                    if (f[i + 1] == true){
                        break;
                    }
                }
            }
            if (f[n] == false){
                return res;
            } else {
                vector<string> temp;
                helper(s, wordDict, temp, res, 0);
                return res;
            }
        }
    };

Log in to reply
 

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