Leetcode 139 / Leetcode 140: word break I II

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

本题是典型的一类一维DP， 类似于cut rope的问题， linear 往回看，如果之前的一段在字典里，那么就看这段之后到当前字符，是否在字典里，如果在，那么包含当前字符的string 在字典里，否则不在字典里。 


class Solution {
private:
    bool find(unordered_set<string>& wordDict, string s) {
        //sanity check
        if (wordDict.size() == 0) return false;
        if (wordDict.find(s) != wordDict.end()) {
            return true;
        } else {
            return false;
        }
    }
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        //sanity check
        if (wordDict.size() == 0 || s.size() == 0) return false;
        bool M[s.size()];
        //base case
        if (find(wordDict, s.substr(0,1))) M[0] = true;
        else M[0] = false;
        for (int i = 1; i < s.size(); i++) {
            if (find(wordDict, s.substr(0, i+1))) {
                M[i] = true;
                continue;
            }
            int j = 0;
            for ( j = 0; j < i; j++) {
                if (find(wordDict, s.substr(j+1, i-j)) && M[j]) {
                    M[i] = true;
                    break;
                }
            }
            if (j == i) M[i] = false;
        }
        return M[s.size()-1];
    }
};

word breakII
DFS+ dp: 利用dp 来记录中间结果，利用dfs来遍历所有可能，dp的结果用来对dfs树进行剪枝，可以减小time complexity。

class Solution {
private:
    void dfs(vector<string> &rst, string solu, string s, bool* M, int start,unordered_set<string>& wordDict) {
        //base case
        if (start == s.size()) {
            solu.resize(solu.size()-1);
            rst.push_back(solu);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            string tmp = s.substr(start, i-start+1);
            if ((M[i+1] || i+1 == s.size()) && (wordDict.find(tmp) != wordDict.end())) {
                int c = solu.size();
                solu += tmp;
                solu += ' ';
                dfs(rst, solu, s, M, i+1, wordDict); //往下遍历的时候start变成了i+1, 因为这一层已经取到了position i..
                solu.resize(c);
            }
        }
    }

public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        vector<string> rst;
        string solu = "";
        if (s.size() == 0) return rst;
        bool M[s.size()];
        //from right to left
        //base case
        if (wordDict.find(s.substr(s.size()-1)) != wordDict.end()) M[s.size()-1] = true;
        else M[s.size()-1] = false;
        for (int j = s.size()-2; j >= 0; j--) {
            //case 1:
            if (wordDict.find(s.substr(j)) != wordDict.end()) M[j] = true;
            else {
               //case2
                int i = 0;
                for (i = j+1; i < s.size(); i++) {
                    if (wordDict.find(s.substr(j, i-j)) != wordDict.end() && M[i]) {
                        M[j] = true;
                        break;
                    }
                }
                if (i == s.size()) M[j] = false;
            }
        }
        if (M[0] == false) return rst;
        dfs(rst, solu, s, M,0, wordDict);
        return rst;
    }
};