LeetCode: Word Break

Solution1:
My DP solution. DPB[i]=true means substring s.substr(0,i) is breakable. so the solution is to find DPB[len].

	public class Solution {
	public boolean wordBreak(String s, Set<String> dict) {
	boolean [] dpb = new boolean[s.length()+1]; //initialized to be false by the compiler
	dpb[0] = true;
	for(int i =0; i < s.length(); i++){
	for(int j=i; j>=0; j--){
	if(dpb[j] == true){
	String tempStr = s.substring(j, i+1);
	for(String str : dict){
	if(str.equals(tempStr))
	dpb[i+1] = true;
	}
	}
	}
	}
	return dpb[s.length()];
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.

For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous iteration in outer loop.

	bool wordBreak(string s, unordered_set<string> &dict) {
	int len = s.length();
	if(len==0) return true;
	if((len == 1) &&(dict.find(s)!=dict.end()))
	return true;
	else if(len == 1)
	return false;
	int *DPB = new int[len+1]; //DPB[i]=true: substr (start from 0, length=i) breakable, find DPB[len]
	for(int i=0; i<=len; i++)
	DPB[i] = false;
	DPB[0] = true;
	DPB[1] = (dict.find(s.substr(0,1)) != dict.end());
	for(int i=1; i<s.length(); i++)
	{
	for(int j=i; j>=0; j--)
	{
	string sub = s.substr(j, i-j+1);
	if((dict.find(sub)!=dict.end()) && DPB[j])
	{
	DPB[i+1]=true;
	break;
	}
	}
	}
	bool res = DPB[len];
	delete []DPB;
	return res;
	}
	Solution2
	class Solution {
	public:
	bool wordBreak(string s, unordered_set<string> &dict) {
	int len = s.length();
	vector<bool> dp(len + 1,false);
	dp[len] = true;
	for (int i = len - 1; i >= 0; i--) {
	for (int j = i; j < len; j++) {
	string str = s.substr(i,j - i + 1);
	if (dict.find(str) != dict.end() && dp[j + 1]) {
	dp[i] = true;
	break;
	}
	}
	}
	return dp[0];
	}
	};

view raw gistfile1.cpp hosted with ❤ by GitHub