LeetCode Q139: 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:

In my first try, I mistakenly compare current substr with ones in the dictionary. If matching, remove the substr from given string and keep matching the remaining part. However, it is not necessarily the correct answer. For example, when s="aaaaaaa", dict=["aaaa", "aaa"], in which the algorithm will match "aaa", "aaa" first, then left only one "a" in s which will result in a failed matching.

So, think of using DP and recursion.

	class Solution {
	public:
	bool helper(string s, int start, unordered_set<string>& wordDict, vector<int>& myH){
	if(s.size()==0){
	myH[start]=1;
	return true;
	}
	bool res=false;
	for(int i=0; i<s.size(); i++){
	string substr=s.substr(0, i+1);
	auto it=wordDict.find(substr);
	if(it!=wordDict.end()){
	if(myH[start+i]==-1){
	myH[start+i]=helper(s.substr(i+1, s.size()-i-1), i+1, wordDict, myH);
	}
	res=res|myH[start+i];
	}
	}
	myH[start]=res==true? 1:0;
	return res;
	}
	bool wordBreak(string s, unordered_set<string>& wordDict) {
	vector<int> myH(s.length()+1, -1);
	bool res=helper(s, 0, wordDict, myH);
	return res;
	}
	};

view raw Q139WordBreak.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int helper(string s, unordered_set<string>& wordDict, unordered_map<size_t, int>& myHash, hash<string>& myHashV){
	if(s.length()==0)
	return true;
	if(myHash[myHashV(s)]!=0)
	return myHash[myHashV(s)];
	for(int i=1; i<=s.length(); i++){
	string w = s.substr(0, i);
	auto it = wordDict.find(w);
	if(it!=wordDict.end()){
	string ss = s.substr(i, s.length()-i);
	int tmp = helper(ss, wordDict, myHash, myHashV);
	if(tmp == 1){
	myHash[myHashV(s)]=1;
	return tmp;
	}
	}
	}
	myHash[myHashV(s)]=-1;
	return -1;
	}
	bool wordBreak(string s, unordered_set<string>& wordDict) {
	unordered_map<size_t, int> myHash;
	hash<string> myHashV;
	int res = helper(s, wordDict, myHash, myHashV);
	return res==1;
	}
	};

view raw Q139Rnd2.cpp hosted with ❤ by GitHub