2014
07-21

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

public class Solution {
public static boolean wordBreak(String s, Set<String> dict) {
if(s==null || s.length()==0) return false;
return find(s,dict);
}
public static boolean find(String s, Set<String> set){
if(s.length() == 0) return true;
boolean find = false;
for(String str:set){
if(s.startsWith(str)){
find =  find(s.substring(str.length()), set);
}
if(find) return true;
}
return false;
}
}

public class WordBreak {
static int dp[][];
static String string;
public static boolean wordBreak(String s, Set<String> dict) {
if(s==null || s.length()==0) return false;
dp = new int[s.length()+1][s.length()+1];
string = s;
return find(0, s.length() ,dict);
}
public static boolean find(int s, int e, Set<String> set){
if(dp[s][e] == -1) return false;
if( s == e || dp[s][e] == 1) return true;
String tmpstr = string.substring(s,e);
boolean find = false;
for(String str:set){
if(tmpstr.startsWith(str)){
find =  find(s+str.length(), e, set);
}
if(find){
dp[s][e] = 1;
return true;
}
}
dp[s][e] = -1;
return false;
}
public static void main(String[] args) {
Set<String> dict = new HashSet<String>();
String str[] = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
System.out.println(wordBreak(s, dict));
}
}

public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] t = new boolean[s.length()+1];
t[0] = true; //set first to be true, why?
//Because we need initial state

for(int i=0; i<s.length(); i++){
//should continue from match position
if(!t[i])
continue;

for(String a: dict){
int len = a.length();
int end = i + len;
if(end > s.length())
continue;

if(t[end]) continue;

if(s.substring(i, end).equals(a)){
t[end] = true;
}
}
}

return t[s.length()];
}
}

1. [email protected]