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".
	Simple recursive(DFS) solution, Time Limitation Exceeded
	failed test case
	Last executed input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
	["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
	public boolean wordBreak(String s, Set<String> dict) {
	if (s==null||s.length()==0){
	return false;
	}
	int start=0;
	return checker(s, start, dict);
	}
	private boolean checker(String s, int start, Set<String> dict){
	if (start==s.length()){
	return true;
	}
	for (int i=start+1; i<=s.length(); i++){
	if (dict.contains(s.substring(start, i))){
	if (checker(s, i, dict)){
	return true;
	}
	}
	}
	return false;
	}
	Cache Solution: record the positon which has been calculated and marked it as true (see cc150 fibonacci cache solution)
	332 mm passed
	public boolean wordBreak(String s, Set<String> dict){
	if (s==null||s.length()==0){
	return false;
	}
	boolean[] checker=new boolean[s.length()];
	Arrays.fill(checker, false);
	for (int i=1; i<=s.length(); i++){
	if (checker[i-1]==false && dict.contains(s.substring(0, i))){
	checker[i-1]=true;
	if (i==s.length()){
	return true;
	}
	}
	if (checker[i-1]==true){
	for (int j=i+1; j<=s.length(); j++){
	if(checker[j-1]==false && dict.contains(s.substring(i, j))){
	checker[j-1]=true;
	if (j==s.length()&&checker[j-1]==true){
	return true;
	}
	}
	}
	}
	}
	return false;
	}
	DP Solution(320 mm passed):
	declare boolean array used to check if given s substring from 0-> given positon-1
	can match given words in dict. then go to check next postion until the end of s.
	In the end return checker[s.length()] wich indicate if given s can split to words in dict
	public boolean wordBreak(String s, Set<String> dict){
	if (s==null || dict==null){
	return false;
	}
	if (dict.size()==0) return s.length()==0;
	boolean[] checker=new boolean[s.length()+1];
	checker[0]=true;
	for (int i=1; i<=s.length(); i++){
	for (int k=0; k<i; k++){
	if (checker[k]&&dict.contains(s.substring(k, i))){
	checker[i]=true;
	}
	if (checker[i]){
	break;
	}
	}
	}
	return checker[s.length()];
	}

view raw Word Break.java hosted with ❤ by GitHub