leetcode：140. 单词拆分 II

题目来源

• leetcode：140. 单词拆分 II

题目描述

题目解析

暴力递归

class Solution {
    

    void process(string &s, std::set<std::string> &dict, int start, std::string &path,  vector<string> &ans){
    
        int N = s.size();
        if(start == N){
    
            ans.push_back(path);
            return;
        }

        for (int end = start; end < N; ++end) {
    
            std::string prefix = s.substr(start, end - start + 1);
            if(dict.count(prefix)){
    
                std::string tmp = path;
                if(tmp.empty()){
    
                    path = prefix;
                }else{
    
                    path = path.append(" ").append(prefix);
                }
                process(s, dict, end + 1, path, ans);
                path = tmp;
            }
        }


    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
    
        std::set<std::string> dict(wordDict.begin(), wordDict.end());
        vector<string> ans;
        std::string path;
        process(s, dict, 0, path, ans);
        return ans;
    }
};

优化：动态规划求是否有解，回溯算法搜索所有符合条件的解

class Solution {
    
    struct Node{
    
        std::string path;
        bool end;
        std::vector<Node *> nexts;

        Node(){
    
            end = false;
            nexts.resize(26);
        }
    };


    Node * getTrie(vector<string>& wordDict){
    
        Node * root = new Node;
        for(auto & word : wordDict){
    
            Node *node = root;
            for(char ch : word){
    
                int idx = ch - 'a';
                if(node->nexts[idx] == nullptr){
    
                    node->nexts[idx] = new Node;
                }
                node = node->nexts[idx];
            }
            node->path = word;
            node->end = true;
        }
        return root;
    }

    std::vector<bool> getDP(string &s, Node *root){
    
        int N = s.size();
        std::vector<bool> dp(N + 1, false);
        dp[N] = true;
        for (int start = N - 1; start >= 0; --start) {
    
            Node *curr = root;
            for (int end = start; end < N; ++end) {
    
                int idx = s[end] - 'a';
                curr = curr->nexts[idx];
                if(curr == nullptr){
    
                    break;
                }
                if(curr->end && dp[end + 1]){
    
                    dp[start] = true;
                    break;
                }
            }
        }
        return dp;
    }

    // str[index.....] 是要搞定的字符串
    // dp[0...N-1] 0... 1.... 2... N-1... 在dp里
    // root 单词表所有单词生成的前缀树头节点
    // path str[0..index-1]做过决定了，做的决定放在path里
    void process(string str, int idx, Node *root,
            std::vector<bool> &dp, std::vector<string>& path,
            std::vector<string> & ans){
    
        if(idx == str.size()){
    
            string builder;
            for (int i = 0; i < path.size() - 1; ++i) {
    
                builder = builder.append(path[i] + " ");
            }
            builder.append(path[path.size() - 1]);
            ans.push_back(builder);
        }else{
    
            Node *curr = root;
            for (int end = idx; end < str.size(); ++end) {
    
                // str[i..end] （能不能拆出来）
                int road = str[end] - 'a';
                curr = curr->nexts[road];
                if(curr == nullptr){
    
                    break;
                }
                if(curr->end && dp[end + 1]){
    
                    path.push_back(curr->path);
                    process(str, end + 1, root, dp, path, ans);
                    path.pop_back();
                }
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
    
        Node * tree = getTrie(wordDict);
        std::vector<bool> dp = getDP(s, tree);
        std::vector<string> path;
        std::vector<string> ans;
        process(s, 0, tree, dp, path, ans);
        return ans;
    }
};