139： Word Break

Q:
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".
A:

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        // treat the whole string,  as appending  each letter at end
        int n = s.length();
        boolean[] blnBreak =  new boolean[n+1];
        blnBreak[0] = true;// the first one is always true, before first char in s
        
        for(int i =0;i<n;i++){
            int j = i;
            while(j>=0 ){
                String lastStr = s.substring(j,i+1); // including ith position
                if(blnBreak[j] && dict.contains(lastStr) ){
                    blnBreak[i+1] = true;
                    break;
                }else{ // not find match
                    j--;
                }
            }
        }
        return blnBreak[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];
    }
}