139. Word Break ----M

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

 

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

A:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        unordered_set<string> S(wordDict.begin(), wordDict.end());
        vector<int> dp(n+1, false);
        dp[0] = true;
        for(int end = 1;  end <=n; end++){
            for(int start = end-1; start>=0; start-- ){
                auto sub = s.substr(start, end-start);
                if(S.find(sub) != S.end() && dp[start]){ // if find it
                    dp[end] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

Mistakes:
1:在 blnBreak里，是用了n+1的size，但是，实际设置的时候， 用的i，还是0到 n-1.
 因此，最后的一个，总是没有设置好。
因此应该用，  blnBreak[i+1] = true;                   而不是blnBreak[i] = true;


--------上面的是记录了前面可以分割的，同样，我们可以每次取下前面的一部分来。后面的递归查找***********

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s==null || s.length()==0)
            return true;
        int[] canBreak = new int[s.length()];
        // canBreak[i] == 0 --> tested, 1--> can break from this position(inclusive) till end, -1-->cannot 
        return helper(s, wordDict, canBreak, 0) > 0;
    }
    private int helper(String s, Set<String> dict,int[] canBreak, int start ){
        int n = s.length(); // start is index, thus always valid
        if( canBreak[start] !=0 )
            return canBreak[start];
        for(int end = start; end <n;end++){
            String frontStr = s.substring(start,end+1);
            if(dict.contains(frontStr)){
                if( end == n-1 || helper(s,dict,canBreak,end+1)>0){
                    canBreak[start] = 1;
                    return canBreak[start];
                }
            }
        }
        canBreak[start] = -1;
        return canBreak[start];
    }
}