LeetCode(140) Word Break II

//30ms
class Solution {
public:
    void dfs(vector<vector<int> > & result_node, int start, vector<int> & path, vector<vector<int> > &paths) {
        if (start == -1) {
            
            // BUG1:
            // C++ pass by value, so first insert into paths, then edit(pop_back(),which holds the value -1) the value of path. 
            // If pop_back() path happens before it is inserted into the paths, then the next round in dfs will be affected.
            paths.push_back(path);
            paths.back().pop_back();
            reverse(paths.back().begin(), paths.back().end());
            return;
        } else {
            for (int i = 0; i < result_node[start].size(); ++i) {

                // BUG2:
                // path.push_back(i);
                path.push_back(result_node[start][i]);
                dfs(result_node, result_node[start][i], path, paths);
                path.pop_back();
            }
        }
    }
    void format_result(string &s ,vector<vector<int> > &paths, vector<string> &final_paths) {
        for (int i = 0; i < paths.size(); ++i) {
            
            // BUG3:
            // the first component of the word string is simply the first word
            // the last delimiter(as in the example, it should be ) should be inserted
            paths[i].push_back(s.length() -1);
            string tmp = s.substr(0, paths[i][0] + 1); 
            
            // BUG4:
            // the second component of the word string is the space sign " " and the word.
            for (int j = 1;j < paths[i].size(); ++j) {
                tmp += " ";
                tmp += s.substr(paths[i][j - 1] + 1, paths[i][j] - paths[i][j - 1]);
            }
            final_paths.push_back(tmp);
        }
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> result_bool(s.length(), false);
        vector<vector<int> > result_node(s.length());
        vector<string> final_paths;
        if (dict.empty()) return final_paths;
        if (dict.find(s) != dict.end()) {
            final_paths.push_back(s);
            return final_paths;
        }
        for (int i = 0; i < result_bool.size(); ++i) {
            if (dict.find(s.substr(0, i + 1)) != dict.end()) {
                result_bool[i] = true;
                result_node[i].push_back(-1);
            }
            for (int j = 0; j < i; ++j) {
                if ((result_bool[j] == true) && (dict.find(s.substr(j + 1, i -j))!= dict.end())) {
                    result_bool[i] = true;
                    result_node[i].push_back(j);
                }
            }
        }
        vector<vector<int> > paths;
        
        // BUG5:
        // similar to Word Break I, use a bool array to record if the word can be segmented.
        // before dfs, should test whether dfs is needed
        if ( !result_bool[s.length() - 1]) {
            return final_paths;
        }
        
        vector<int> path;
        dfs(result_node, result_node.size() - 1, path, paths);
        format_result(s, paths, final_paths);
        return final_paths;
    }
};