[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);
	}
};