Word Break

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Have you met this question in a real interview? 

Yes

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here  
        int len = s.length();
        boolean[] record = new boolean[len+1];
        record[0] = true;
        // get the max word length of wordDict
        int max_word_len = 0;
        for (String word : dict) {
            max_word_len = Math.max(max_word_len, word.length());
        }
        for(int i = 0; i < len; i++){
           
            for(int j = i; j>= 0; j--){
                 if (i - j > max_word_len) break;
                String sub = s.substring(j, i+1);
                if(dict.contains(sub) && record[j]){
                    record[i+1] = true;
                    break;
                }
            }
        }
        return record[len];
    }
}