Word Break (Dynamic Programming)

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

Idea: Dynamic programming. Let dp[i] denotes from s[0]->s[i-1] can be partitioned, then dp[s.length()] is the result. For each position i, use all the words in the dict to "jump" where "jump" means if a word (assumes length x)contained in the dict matches a portion of the input string, set dp[i+x]=true. If we can finally reach the end of the input string, that means all the substrings along the way can be found in the dict.

Time: O(m*n) Space: O(m), where m is the length of the input string, n is the size of the dictionary.

Code:

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     int n=s.length();  
     boolean[] dp=new boolean[n+1];  
     dp[0]=true;  
     for(int i=0;i<n;i++)  
     {  
       if(dp[i]==false)  
         continue;  
       for(String word:dict)  
       {  
         int len=word.length();  
         int end=i+len;  
         if(end>s.length())  
           continue;  
         if(dp[end]==true)  
           continue;  
         if(s.substring(i,end).equals(word))  
           dp[end]=true;  
       }  
     }  
     return dp[n];  
   }  
 }