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".

Solution:
dp[i] represents from 0 to i-1 position, if the string can be segmented.

1. initialize dp[string_len + 1], dp[0] = true
2. two indexes, i and j i traverses from 0 to the end j traverses from 0 to the i if substring(0,j)is in the dic ---> (dp[j] == true) and substring (j,i) is in the dictionary, update dp[i] = true
3. return dp[string_len]

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null){
            return true;
        }
        //f[i] represent from 0th position to i-1 position can be breaked
        //with dictionary word
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for(int i = 0; i < s.length(); i++){
            for(int j = i; j >= 0; j--){
                if(f[j] && wordDict.contains(s.substring(j, i+1))){
                    f[i+1] = true;
                }
            }
        }
        return f[s.length()];
    }
}