【动态规划】【字符串】C++算法：140单词拆分

作者推荐

【动态规划】【字符串】扰乱字符串

本文涉及的基础知识点

动态规划字符串

LeetCode140:单词拆分 II

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 1：
输入:s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
输出:[“cats and dog”,“cat sand dog”]
示例 2：
输入:s = “pineapplepenapple”, wordDict = [“apple”,“pen”,“applepen”,“pine”,“pineapple”]
输出:[“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”]
解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:s = “catsandog”, wordDict = [“cats”,“dog”,“sand”,“and”,“cat”]
输出:[]
参数范围：
1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

动态规划

n = s.length
分两步：
一，计算所有子串是否存在相等的word，如果存在记录其下标，不存在-1。
二，通过动态规划计算所有所有前缀可以组成的字符串。

动态规划分析


动态规划的状态表示	dp[i]记录s[0,)所有可能组成的字符串
动态规划的转移方程	vIndex[left][i - 1]不为-1，则dp[left]可以和[left,i)拼接
动态规划的初始状态	dp[0]有一个空字符串
动态规划的填表顺序	i从小到大。由短到长处理子字符串,确保动态规划的无后效性
动态规划的返回值	dp.back()

代码

核心代码

class Solution {
public:
	vector<string> wordBreak(string s, vector<string>& wordDict) {
		m_c = s.length();
		unordered_map<string, int> mStrIndex;
		for (int i = 0; i < wordDict.size(); i++)
		{
			mStrIndex[wordDict[i]] = i;
		}
		vector<vector<int>> vIndex(m_c, vector<int>(m_c, -1));
		for (int i = 0; i < m_c; i++)
		{
			for (int j = i; j < m_c; j++)
			{
				const auto tmp = s.substr(i, j - i + 1);
				if (mStrIndex.count(tmp))
				{
					vIndex[i][j] = mStrIndex[tmp];
				}
			}
		}

		vector<vector<string>> dp(m_c+1);
		dp[0].emplace_back("");
		for (int i = 1; i <= m_c; i++)
		{
			for (int left = 0; left < i; left++)
			{
				const int inx = vIndex[left][i - 1];
				if (-1 == inx)
				{
					continue;
				}
				for (string s : dp[left])
				{
					dp[i].emplace_back(s + (s.empty() ? "" : " ") + wordDict[inx]);
				}
			}
		}
		return dp.back();
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	string s;	
	vector<string> wordDict;
	{
		Solution sln;
		s = "catsanddog", wordDict = { "cat", "cats", "and", "sand", "dog" };
		auto res = sln.wordBreak(s, wordDict);
		Assert(vector<string>{"cats and dog", "cat sand dog"}, res);
	}
	{
		Solution sln;
		s = "pineapplepenapple", wordDict = { "apple", "pen", "applepen", "pine", "pineapple" };
		auto res = sln.wordBreak(s, wordDict);
		Assert(vector<string>{"pine apple pen apple", "pineapple pen apple", "pine applepen apple"}, res);
	}
	{
		Solution sln;
		s = "catsandog", wordDict = { "cats", "dog", "sand", "and", "cat" };
		auto res = sln.wordBreak(s, wordDict);
		Assert(vector<string>{}, res);
	}
}

2023年1月

class Solution {
public:
vector wordBreak(string s, vector& wordDict) {
m_c = s.length();
m_vPosWord.resize(s.length());
for (int i = 0; i < wordDict.size();i++ )
{
const auto& f = wordDict[i];
int iPrePos = 0;
while (true)
{
int iPos = s.find(f, iPrePos);
if (-1 == iPos)
{
break;
}
m_vPosWord[iPos].push_back(i);
iPrePos = iPos + 1;
}
}
m_pWords = &wordDict;
dfs(0);
return m_vRet;
}
void dfs(int iPos)
{
if (iPos >= m_c)
{
string s = “”;
for (int i = 0; i < m_vIndexWord.size(); i++)
{
if (0 != i)
{
s += " ";
}
s += (*m_pWords)[m_vIndexWord[i]];
}
m_vRet.push_back(s);
return;
}
for (const auto& f : m_vPosWord[iPos])
{
m_vIndexWord.push_back(f);
dfs(iPos + (m_pWords)[f].length());
m_vIndexWord.pop_back();
}
}
vector m_vRet;
vector<vector> m_vPosWord;
vector m_vIndexWord;
vector m_pWords;
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛