【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数_网站优化分享

您的位置：上海毫米网络优化公司 > 网站优化分享 >

作者推荐

【动态规划】【字符串】【行程码】1531. 压缩字符串

本文涉及知识点

动态规划汇总

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

1639. 通过给定词典构造目标字符串的方案数

给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都长度相同。

你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：

从左到右依次构造 target 的每一个字符。

为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。

一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。

请你重复此过程直到得到目标字符串 target 。

请注意，在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中同一个字符串的多个字符。

请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 109 + 7 取余后返回。

（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

示例 1：

输入：words = [“acca”,“bbbb”,“caca”], target = “aba”

输出：6

解释：总共有 6 种方法构造目标串。

“aba” -> 下标为 0 (“acca”)，下标为 1 (“bbbb”)，下标为 3 (“caca”)

“aba” -> 下标为 0 (“acca”)，下标为 2 (“bbbb”)，下标为 3 (“caca”)

“aba” -> 下标为 0 (“acca”)，下标为 1 (“bbbb”)，下标为 3 (“acca”)

“aba” -> 下标为 0 (“acca”)，下标为 2 (“bbbb”)，下标为 3 (“acca”)

“aba” -> 下标为 1 (“caca”)，下标为 2 (“bbbb”)，下标为 3 (“acca”)

“aba” -> 下标为 1 (“caca”)，下标为 2 (“bbbb”)，下标为 3 (“caca”)

示例 2：

输入：words = [“abba”,“baab”], target = “bab”

输出：4

解释：总共有 4 种不同形成 target 的方法。

“bab” -> 下标为 0 (“baab”)，下标为 1 (“baab”)，下标为 2 (“abba”)

“bab” -> 下标为 0 (“baab”)，下标为 1 (“baab”)，下标为 3 (“baab”)

“bab” -> 下标为 0 (“baab”)，下标为 2 (“baab”)，下标为 3 (“baab”)

“bab” -> 下标为 1 (“abba”)，下标为 2 (“baab”)，下标为 3 (“baab”)

示例 3：

输入：words = [“abcd”], target = “abcd”

输出：1

示例 4：

输入：words = [“abab”,“baba”,“abba”,“baab”], target = “abba”

输出：16

提示：

1 <= words.length <= 1000

1 <= words[i].length <= 1000

words 中所有单词长度相同。

1 <= target.length <= 1000

words[i] 和 target 都仅包含小写英文字母。

动态规划

动态规划的状态表示

vCan[i][j] 如果包括x，words有几个元素的下标j 是’a’+i。

pre[j] 表示words[?][0,j)和target[0,i)匹配。dp[j]表示 words[?][0,j)和target[0,i+1)匹配。

动态规划的转移方程

dp[j] = ∑ k = 0 j \Large\sum_{k=0}^{j} ∑k=0jpre[k]

vCan[i]必须包括j。

动态规划的初始值

pre[0]=1，其它全为0。

动态规划的填表顺序

i从小到大，j从小到大。

动态规划的返回值

pre的和。

代码

核心代码

template
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{
	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};
class Solution {
public:
	int numWays(vector& words, string target) {
		m_c = words[0].size();
		vector> vCan(26,vector(m_c));
		for (int i = 0; i < m_c; i++)
		{
			for (int j = 0; j < words.size(); j++)
			{
				const int index = words[j][i] - 'a';
				vCan[index][i]++;
			}
		}
		vector> pre(m_c + 1);
		pre[0] = 1;
		for (int i = 0; i < target.size(); i++)
		{
			vector> dp(m_c + 1);
			C1097Int<> biSum = 0;
			int k = 0;
			for (int j = 0 ; j < m_c ; j++ )
			{
				while (k <= j)
				{
					biSum += pre[k++];
				}
				dp[j+1] = biSum*vCan[target[i]-'a'][j];
			}
			pre.swap(dp);
		}
		return std::accumulate(pre.begin(), pre.end(), C1097Int<>()).ToInt();
	}
	int m_c;
};

核心代码

template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}
int main()
{	
	vector words;
	string target;
	{
		Solution sln;
		words = { "acca", "bbbb", "caca" }, target = "aba";
		auto res = sln.numWays(words, target);
		Assert(res, 6);
	}
	{
		Solution sln;
		words = { "abba", "baab" }, target = "bab";
		auto res = sln.numWays(words, target);
		Assert(res, 4);
	}
	{
		Solution sln;
		words = { "abcd" }, target = "abcd";
		auto res = sln.numWays(words, target);
		Assert(res, 1);
	}
	{
		Solution sln;
		words = { "abab", "baba", "abba", "baab" }, target = "abba";
		auto res = sln.numWays(words, target);
		Assert(res, 16);
	}
}

2023年2月

class C1097Int

{

public:

C1097Int(int iData = 0) :m_iData(iData)

{

 }
 C1097Int  operator+(const C1097Int& o)const
 {
	 return C1097Int((m_iData + o.m_iData) % s_iMod);
 }
 C1097Int&  operator+=(const C1097Int& o)
 {
	 m_iData = (m_iData + o.m_iData) % s_iMod;
	 return *this;
 }
 C1097Int  operator*(const C1097Int& o)const
 {
	 return((long long)m_iData *o.m_iData) % s_iMod;
 }
 C1097Int&  operator*=(const C1097Int& o)
 {
	m_iData =((long long)m_iData *o.m_iData) % s_iMod;
	 return *this;
 }
 int ToInt()const
 {
	 return m_iData;
 }

private:

int m_iData = 0;;

static const int s_iMod = 1000000007;

};

int operator+(int iData, const C1097Int& int1097)

{

int iRet = int1097.operator+(C1097Int(iData)).ToInt();

return iRet;

}

int& operator+=(int& iData, const C1097Int& int1097)

{

iData = int1097.operator+(C1097Int(iData)).ToInt();

return iData;

}

class Solution {

public:

int numWays(vector& words, string target) {

m_r = words.size();

m_c = words[0].size();

m_vCharNums.assign(m_c, vector(26));

for (int r = 0; r < m_r; r++)

{

for (int c = 0; c < m_c; c++)

{

m_vCharNums[c][words[r][c] - ‘a’]++;

}

// 已经处理完的target串对应words[?]的前pre[i]个字符

vector pre(m_c + 1);

pre[0] = 1;

for (const auto& ch : target)

{

vector dp(m_c + 1);

C1097Int iSub = 0;

for (int j = 1; j <= m_c; j++)

{

iSub += pre[j - 1];

dp[j] = iSub * m_vCharNums[j - 1][ch - ‘a’];

}

pre.swap(dp);

}

return std::accumulate(pre.begin(), pre.end(), C1097Int(0)).ToInt();

}

int m_r;

int m_c;

vector m_vCharNums;

};

【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数,第1张

扩展阅读

视频课程

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

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

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

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数,第2张

dreamweaver网页制作教程网站制作公司咨询万网空间登录重庆网站设计制作公司官网格式设计交互设计软件

上一篇：【C++】C++11 ~ 右值引用和移动语义

下一篇：算法沉淀——二叉树中的深搜（leetcode真题剖析）

作者推荐

本文涉及知识点

1639. 通过给定词典构造目标字符串的方案数

动态规划

动态规划的状态表示

动态规划的转移方程

动态规划的初始值

动态规划的填表顺序

动态规划的返回值

代码

核心代码

核心代码

2023年2月

扩展阅读

视频课程

相关

测试环境