[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".

问题描述：给定一个字符串s和一个由单词组成的字典dict，判断是否能够将s分段成一个或者多个字典中的单词。

对于s，可以有很多种进行分段的方式，如果在这些分段方式中至少有一种情况：被截断的各个部分都是dict中的单词，那么，s就能够分段成一个或者多个字典中的单词。因此，最简单的想法是，如果能够得到一个单词的所有分段形式，然后遍历这些分段序列，直到有一种分段情况下，所有的单词都是dict中的单词，那么，就返回true，没有找到，就返回false。当然，这种方法是不现实的。

为了判断，就必须进行分段。首先，将[beg, end)引用的字符串分成[beg, sep)和[sep, end)，sep必须从beg+1一直到end，如果其中有一种情况，两个区间的字符串可以进行分段，那么[beg, end)就可以进行分段。然后就需要递归判断两个字符串是否可以进行分段。但是只能对[beg, sep)和[sep, end)中的一个使用递归的判断函数，因为，这样做复杂度太高，因此，只对[sep, end)使用递归的判断函数，对[beg, sep)使用dict来判断。于是有下面的代码：

bool word(string::iterator beg, string::iterator end,
		unordered_set
  
    &dict) 
	{
		if(beg == end) {
			return true;
		}

		if(dict.find(string(beg, end)) != dict.end()) {
			return true;
		}

		string::iterator sep = beg + 1;
		while(sep != end) {
			if(dict.find(string(beg, sep)) != dict.end() && word(sep, end, dict)) {
				return true;
			}
			++sep;
		}
		return false;
	}

	bool wordBreak(string s, unordered_set
   
     &dict) { if(s.empty()) return false; return word(s.begin(), s.end(), dict); }
   
  

TIme Limit Exceeded

超时了，说明算法的时间复杂度还是太高了，要设法进行优化。当进行递归时，如果分支中重复的分支很多，就可以使用动态规划。在判断[sep, end)时，使用了递归函数word，但是，如果对一个字符串进行考察可以知道，其中有很多重复判断，因此，必须减少重复判断，也就是增加记忆功能，将已经判断失败的字符串保存起来，当判断一个字符串时，可以先与失败的字符串比较，如果是失败的字符串，就继续下一轮判断，这样，可以加快判断。

class Solution {
public:
    bool word(string::iterator beg, string::iterator end, unordered_set
  
    &dict, set
   
      _seg) { if(beg == end) return true; if(dict.find(string(beg, end)) != dict.end()) { return true; } string::iterator sep = beg + 1; while(sep != end) { if(dict.find(string(beg, sep)) != dict.end() && dict.find(string(sep, end)) != dict.end()) { return true; } if(dict.find(string(beg, sep)) != dict.end()) { if(not_seg.find(string(sep, end)) == not_seg.end()) { if(word(sep, end, dict, not_seg)) { return true; } else { not_seg.insert(string(sep, end)); } } } ++sep; } not_seg.insert(string(beg, end)); return false; } bool wordBreak(string s, unordered_set
    
      &dict) { if(s.empty()) return false; set
     
       not_seg; return word(s.begin(), s.end(), dict, not_seg); } };