word break.java

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        if(len == 0)
            return dict.contains(s);
        boolean[] record = new boolean[len];
        for(int i = 0; i < len; ++i){
            if(dict.contains(s.substring(0,i + 1))){
                record[i] = true;
                continue;
            }
            for(int j = 0; j < i; ++j){
                if(record[j] && dict.contains(s.substring(j + 1, i + 1))){
                    record[i] = true;
                    break;
                }
            }
        }
        return record[len - 1];
    }
}