[LeetCode]Word Break II

和Word Break是一样的，递归的题目。可以用recursion with memorization或者dp来做。
Recursion with memorization的做法如下，时间复杂度O(n^2 * k)，k为string前i个char能break出来string的平均数量。对于每个i，我们存其可以break的所有结果，平均k个结果，长度为i + 1，空间复杂度O(n^2 * k)：

	class Solution {
	public:
	vector<string> wordBreak(string s, vector<string>& wordDict) {
	unordered_set<string> dict(wordDict.begin(), wordDict.end());
	unordered_map<int, vector<string>> cache;
	return backtracking(s, 0, dict, cache);
	}
	private:
	vector<string> backtracking(const string& s, int i, unordered_set<string>& wordDict, unordered_map<int, vector<string>>& cache)
	{
	int len = s.size();
	if(i == len)return {""};
	if(cache.find(i) != cache.end())return cache[i];
	vector<string> res;
	for(int j = len - 1; j >= i; --j)
	{
	string str = s.substr(i, j - i + 1);
	if(wordDict.find(str) != wordDict.end())
	{
	auto sub = backtracking(s, j + 1, wordDict, cache);
	if(sub.size())
	{
	for(auto s : sub)
	{
	s = s.empty()? str: str + " " + s;
	res.push_back(s);
	}
	}
	}
	}
	cache[i] = res;
	return res;
	}
	};

view raw Word Break II_1.cpp hosted with ❤ by GitHub

DP的做法如下，时间复杂度O(n^2 * k)，空间复杂度O(n^2 * k)：

	class Solution {
	public:
	vector<string> wordBreak(string s, vector<string>& wordDict) {
	int len = s.size();
	unordered_set<string> dict(wordDict.begin(), wordDict.end());
	vector<vector<string>> dp(len + 1);
	dp[0] = {""};
	for(int i = 0; i < len; ++i)
	{
	for(int j = 0; j <= i; ++j)
	{
	string str = s.substr(j, i - j + 1);
	if(dict.find(str) != dict.end() && dp[j].size())
	{
	auto sub = dp[j];
	for(auto s : sub)
	{
	s = s.empty()? str: s + " " + str;
	dp[i + 1].push_back(s);
	}
	}
	}
	}
	return dp[len];
	}
	};

view raw Word Break II_2.cpp hosted with ❤ by GitHub