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

分析：先以最短的划分，先判断以最短的开头是否能分成词，递归判断。但是出现超时如下：

代码1：超时的代码

Last executed input:"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

class Solution{
public:
	bool wordBreak(string s, unordered_set<string> &dict) {
		if(s.empty() || dict.empty()){
			return false;
		}
		return wordBreak(s,0,dict);
	}
	bool wordBreak(string s,int start,unordered_set<string>& dict){
		for(int i=start; i<s.length();++i){
			if(dict.find(s.substr(start,i-start+1))!=dict.end()){
				if(i+1==s.length()||wordBreak(s,i+1,dict)){
					return true;
				}
			}
		}
		return false;
	}
};

代码2、上述超时原因很明显，是每次判断最短的，判断次数太多，那么如何减少这个判断次数呢？如果从最长判断还是会出现这种判断次数太多的结果。

有点无从下手，搜索参考http://www.cnblogs.com/easonliu/p/3654123.html，其中应用了动态规划的方法。

思路：用vector<bool> dp来保存字符串位置i及以前的字符串能否被分解为单词，如果dp[i]==true，则判断i后面的长度为len的字串能否被分解为单词，更新dp[i+len]。这样避免了子问题多次求解的问题。

代码如下：

class Solution {
public:
   bool wordBreak(string s, unordered_set<string> &dict) {
        int n = (int)s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                for (int len = 1; i + len - 1 < n; len++) {
                    if (dict.count(s.substr(i, len)) > 0)
                        dp[i + len] = true;
                }
            }
        }
        return dp[n];
    }
};

修改：

上述代码需要遍历结束所有的，其实只要有一个满足条件就可以了，就是当其中一个i和len满足i+len == n并且dict.count(s.substr(i, len))>0时即可，这样运行时间要短一些。

如下：

class Solution {
public:
   bool wordBreak(string s, unordered_set<string> &dict) {
        int n = (int)s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                for (int len = 1; i + len - 1 < n; len++) {
                    if (dict.count(s.substr(i, len)) > 0)
                    {
                        if( i+len == n){
                            return true;
                        }
                        dp[i + len] = true;
                    }
                        
                }
            }
        }
        return dp[n];
    }
};

2、Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

分析：此题和上题类似，也可以采用动态规划的方法。

代码1：超内存的代码。用vector来保存截止到每个位置之前可以分解为单词的所有组合，但是这样耗费内存太多。

Memory Limit Exceeded

class Solution {
public:
	vector<string> wordBreak(string s, unordered_set<string> &dict) {
		int n = (int)s.size();
		vector<bool> dp(n + 1, false);
		vector<vector<string>> allWords(n+1); 
		dp[0] = true;
		for (int i = 0; i < n; i++) {
			if (dp[i]) {
				vector<string> tempVector = allWords[i];
				for (int len = 1; i + len - 1 < n; len++) {
					string subStr = s.substr(i, len);
					if (dict.count(subStr) > 0)
						if(allWords[i].empty()){
							allWords[i+len].push_back(subStr);
						}else{
							for(int j=0; j<allWords[i].size();++j){
								allWords[i+len].push_back(allWords[i][j]+" "+subStr);
							}
						}
						dp[i + len] = true;
				}
			}
		}
		return allWords[n];
	}
};

那么如何节约内存呢？想着记录每个点的前一个分割点的值，然后遍历得到所有可能的值，但是如何输出感觉不容易。。。

先附上一个搜到的通过的代码，后续再来补讲解。

class Solution {
public:
	vector<string> wordBreak(string s, unordered_set<string> &dict) 
	{
		int n=s.length();
		vector<vector<bool> > match(n+1,vector<bool>(n+1,false));
		for(int i=0;i<=n;i++)
			match[0][i]=true;
		for(int len=1;len<=n;len++)
		{
			for(int start=0;start+len<=n;start++)
			{
				string tmp=s.substr(start,len);
				if(dict.count(tmp)>0)
					match[len][start]=true;
				else
				{
					for(int left=1;left<len;left++)
					{
						match[len][start]=match[left][start]&&match[len-left][start+left];
						if(match[len][start])
							break;
					}
				}
			}
		}
		if(match[n][0]==false)
			return vector<string>();
		vector<string> ans;
		vector<string> had;
		dfs(s,0,match,had,ans,dict);
		return ans;
	}
	void dfs(string& s,int k,vector<vector<bool> >& match,vector<string>& had,vector<string>& ans,unordered_set<string> &dict)
	{
		int n=s.length();
		if(k>=n)
		{
			if(!had.empty())
			{
				string ret;
				for(int i=0;i<had.size();i++)
				{
					ret.append(had[i]);
					if(i!=had.size()-1)
						ret.push_back(‘ ‘);
				}
				ans.push_back(ret);
				return;
			}
		}
		for(int len=1;k+len<=n;len++)
		{
			string tmp=s.substr(k,len);
			if(dict.count(tmp)>0 && match[n-k-len][k+len])
			{
				had.push_back(tmp);
				dfs(s,k+len,match,had,ans,dict);
				had.pop_back();
			}
		}
	}	
};

leetcode day7 -- Word Break I II