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:
first try: split s... 
second try: iterate dict & recursion -> Time Limit Exceeded 
third try: dp: dp[i] donates 0...i can be segmented. bottom-up. 

// bottom up!!!!!!!!!!!!!!!!!!!!!!
public class Solution {
    public boolean wordBreak(String s, Set dict) {
        int n = s.length();
        
        // dp[n] donates substring 0...n can be segmented or not
        boolean[] dp = new boolean[n];
        Arrays.fill(dp,false);
        
        for(int i = 0; i < n; i++){
            if(i > 0 && !dp[i-1])
                continue;
            for(String str : dict){
                int len = str.length();
                if ((i + len - 1) < n && s.substring(i,i+len).equals(str))
                    dp[i+len-1] = true;
            }    
        }
        
        return dp[n-1];
    }
}