leetcode：139. 单词拆分

题目来源

• leetcode：139. 单词拆分

题目描述

题目解析

暴力超时

思路

递归树：

class Solution {
    
    bool process(string &s, int start, std::set<std::string> &dict){
    
        int N = s.size();
        if(start == N){
    
            return true;
        }

        
        for (int end = start; end < N; ++end) {
    
            std::string prefix = s.substr(start, end - start + 1);
            if(dict.count(prefix) && process(s, end + 1, dict)){
    
                return true;
            }
        }
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    
        std::set<std::string> dict;
        for(auto &w : wordDict){
    
            dict.insert(w);
        }
        return process(s, 0, dict);
    }
};

加备忘录过。

动态规划

class Solution {
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    
        std::set<std::string> dict;
        for(auto &w : wordDict){
    
            dict.insert(w);
        }

        int N = s.size();
        std::vector<bool> dp(N + 1, false);
        dp[N] = true;
        for (int start = N - 1; start >= 0; --start) {
    
            for (int end = start; end < N; ++end) {
    
                std::string prefix = s.substr(start, end - start + 1);
                if(dict.count(prefix) && dp[end + 1]){
    
                    dp[start] = true;
                    break;
                }
            }
        }
        
        return dp[0];
    }
};

前缀树优化

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

        Node(){
    
            end = false;
            nexts.resize(26);
        }
    };
public:
    bool wordBreak(string s, vector<string>& wordDict) {
    
        Node *root = new Node();
        for(auto &w : wordDict){
    
            Node *node = root;
            int idx = 0;
            for (char i : w) {
    
                idx = i - 'a';
                if(node->nexts[idx] == nullptr){
    
                    node->nexts[idx] = new Node();
                }
                node = node->nexts[idx];
            }
            node->end = true;
        }

        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) {
    
                char ch = s[end];
                curr = curr->nexts[ch - 'a'];
                if(curr == nullptr){
    
                    break;
                }
                if(curr->end && dp[end + 1]){
      // i...end 真的是一个有效的前缀串 end+1.... 能不能被分解
                    dp[start] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
};