Leetcode - WordBreak III

Given a string s and a dictionary of words dict, determine if s can be segmented into a sequence of one or more dictionary words.

   But notice that each word in the dictionary can be used at most once.

For example:

  the dictionary is {"leet", "co" "de" "code"}

  It can match "leetcode", can match “leetcodecode”，but can’t match “leetleetcode”
 [分析] 此题为yb君改编，改编后的题目不能采用动态规划来做，动态规划要求问题的各求解方案是独立平行的，改编后一步决策会影响下一步，因此需要回溯。思维混乱或者貌似空白时把每一点想法尽可能的描述出来，这非常有助于形成完整的思路。

 

boolean IsComposible(Set<String> dict, String s) {
	if (dict == null || s == null || s.length() == 0)
		return false;
	if (dict.contains(s))
		return true;
	int n = s.length();
	for (int i = 1; i <= n; i++) {
		String substr = s.substring(0, i);
		if (dict.contains(substr)) {
			dict.remove(substr);
			if (isComposible(dict, s.substring(i, n)))
				return true;
			dict.add(substr);
		}
	}
	return false;
}

// 下面代码为扩展题，给出一种方案
ArrayList<String> IsComposible(Set<String> dict, String s) {
	ArrayList<String> result = new ArrayList<String>();
	dowork(dict, s, result);
	return result;
}

boolean dowork(Set<String> dict, String s, ArrayList<String> comp) {
	if (s == null || s.length() == 0)
		return true;
	if (dict == null)
		return false;
	
	int n = s.length();
	for (int i = 1; i <= n; i++) {
		String substr = s.substring(0, i);
		if (dict.contains(substr)) {
			dict.remove(substr);
			comp.add(substr);
			if (dowork(dict, s.substrin(i, n), comp))
				return true;
			dict.add(substr);
			comp.removeAt(comp.size() - 1);
		}
	}
	return false;
}