139. Word Break

we use a array dp to denote whether substring of s can be segmented into words in dictionary. If dp[i] = true, then s.substring(0, i) can be segmented into words in dictionary. If dp[s.length()] is true, then s can be segmented into words in dictionary.

At first, we set dp[0] to true and then we traverse s.substring(0, i) where i begins at 1 and ends at s.length().

For each substring s.substring(0, i), if there exists j where

1. 0 <= j < i
2. dp[j] == true and
3. s.substring(j, i) exists in wordDict

Then s.substring(0, i) can also be segmented into words in wordDict.

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<String>(wordDict);
    boolean dp[] = new boolean[s.length() + 1];
    dp[0] = true;
    for(int i = 1; i <= s.length(); i++) {
	for(int j = 0; j < i; j++) {
	    if( dp[j] && wordSet.contains(s.substring(j, i)) ) {
		dp[i] = true;
		break;
	    }
	}
    }
    return dp[s.length()];
}