139. Word Break

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. set the begining to be a dummy char, and the set default value to be true.

dp[i] = dp[k] && substring(k+1, i+1) in the dict. k = [0..i)

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] res = new boolean[s.length() +1];
        String t = "*" + s;
        res[0] = true;

        for(int i=1; i< t.length(); i++){
            for(int k = 0; k< i; k++){
                res[i] = res[k] && wordDict.contains(t.substring(k+1, i+1)); // this is i+1 cause we are calculating res[i], so charAt(i) should be included;
                if(res[i]) break;
            }
        }

        return res[res.length-1];
    }
}