Leetcode 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 1: Use DP, dp[i] stores if [0...i] can be break or not.

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