8ms BFS + DFS C++ solution.


  • 0
    S

    Idea is to use BFS path to build reverse DAG where edges will go from end to start of the words.
    Using this DAG build all paths from the last position of the string.

    An example:
    s = "catsanddog",
    dict = ["cat", "cats", "and", "sand", "dog"].

    Using BFS following graph will be built:

    10 -> 7 -> 3 - > 0
           \
            -> 4 -> 0
    

    During dfs we maintaining current path and once we have start position == 0 we have
    full path and can build using reverse order.

    class Solution {
    public:
    
        string rconcat(const vector<string>& path) {
            bool first = true;
            string result;
            for (auto it = path.rbegin(); it != path.rend(); ++it) {
                if (!first) result.append(" ");
                first = false;
                result.append(*it);
            }
            return result;
        }
    
        void dfs(map<int, vector<int>>& tree,
                 int from, int to, const string& s, 
                 vector<string>& path,
                 vector<string>& results) {
            path.push_back(s.substr(from, to-from));
            if (from == 0) {
                results.push_back(rconcat(path));
            } else {
                for (int i = 0; i < tree[from].size(); i++) {
                    dfs(tree, tree[from][i], from, s, path, results);
                }
            }
            path.pop_back();
        }
    
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            vector<string> res;
            
            queue<int> bfs;
            unordered_set<int> visited;
            unordered_set<string> dict;
            for (const auto& w: wordDict) dict.insert(w);
            
            map<int, vector<int>> tree;
            
            bfs.push(0);
            while (!bfs.empty()) {
                int start = bfs.front(); bfs.pop();
                if (visited.find(start) == visited.end()) {
                    visited.insert(start);
                    for (int j = start+1; j <= s.size(); j++) {
                        auto substr = s.substr(start, j-start);
                        if (dict.find(substr) != dict.end()) {
                            bfs.push(j);
                            tree[j].push_back(start);
                        }
                    }
                }
            }
            
            if (tree.find(s.size()) == tree.end()) return res;
            vector<string> path;
            for (int i = 0; i < tree[s.size()].size(); i++) {
                dfs(tree, tree[s.size()][i], (int)s.size(), s, path, res);
            }
            return res;
        }
    };
    

Log in to reply
 

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