word-break-ii

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

题解

本想在上一题基础上改一改，结果超出时间限制。需要先验证能否拆分，如果直接求字符串，一些用例会内存超限。

vector<string> wordBreak(string s, vector<string>& wordDict) {
	if (!wordBreak2(s, wordDict))return{};
	vector<vector<string>> dp(s.size() + 1, vector<string>());
	for (int i = 0; i < s.length(); i++)
	{
		if (i&&dp[i].empty())continue;
		for (string word : wordDict)
		{
			int wlen = word.length();
			int newEnd = i + wlen;
			if (newEnd > s.length())continue;
			if (s.compare(i, wlen, word, 0, wlen))continue;
			if (i == 0)
			{
				dp[newEnd].push_back(word);
				continue;
			}
			for (string d : dp[i])
				dp[newEnd].push_back(d + " " + word);
		}
	}
	return dp.back();
}