【动态规划】【字符串】【前缀和】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=0j​pre[k]
vCan[i]必须包括j。

动态规划的初始值

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

动态规划的填表顺序

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

动态规划的返回值

pre的和。

代码

核心代码

template<int MOD = 1000000007>
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<string>& words, string target) {
		m_c = words[0].size();
		vector<vector<int>> vCan(26,vector<int>(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<C1097Int<>> pre(m_c + 1);
		pre[0] = 1;
		for (int i = 0; i < target.size(); i++)
		{
			vector<C1097Int<>> 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<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()
{	
	vector<string> 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<vector> m_vCharNums;
};

扩展阅读

视频课程

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

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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/360703.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

编译Opencv3.3.1遇到的编译器无法识别的警告的问题解除：

编译Opencv3.3.1遇到的编译器无法识别的警告的问题解除：

问题描述&#xff1a; 本文&#xff0c;就是在一个硬件的SDK中用到了opencv3.3.1的版本&#xff0c;在笔者目前的VS2019,CUDA11版本下编译的问题和解决。在做Cmake的configure的时候&#xff0c;Cmake报了一个找不到编译器版本的错误, Selecting windows SDK version 10.0.1904…
阅读更多...
TOP100 矩阵

TOP100 矩阵

1.73. 矩阵置零 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 提示&#xff1a; m matrix.lengthn matrix[0].length1 < m, n < 200-2^31 < matrix[i][j] < 2^31 - 1 思路&#xf…
阅读更多...
EMQX 单机及集群搭建

EMQX 单机及集群搭建

目录 1. 通过 Yum 源安装&#xff08;CentOS7 单机安装&#xff09; 1.1. 通过以下命令配置 EMQX Yum 源&#xff1a; 1.2. 运行以下命令安装 EMQX&#xff1a; 1.3. 运行以下命令启动 EMQX&#xff1a; 1.4. 访问 http://192.168.88.130:18083&#xff0c;默认用户名: adm…
阅读更多...
Java项目要不要部署在Docker里？

Java项目要不要部署在Docker里？

部署Java项目有很多种方式&#xff0c;传统的方式是直接在物理机或虚拟机上部署应用&#xff0c;但为什么现在容器化部署变得越来越流行&#xff0c; 个人觉得原因有以下几个&#xff1a; 1、 环境一致性&#xff1a;使用Docker可以确保开发、测试和生产环境的一致性&#xff…
阅读更多...
如何使用保留可探测字段参数的方法解决视频监控管理平台EasyCVR无法启动的问题

如何使用保留可探测字段参数的方法解决视频监控管理平台EasyCVR无法启动的问题

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…
阅读更多...
飞桨paddlespeech语音唤醒推理C INT8 定点实现

飞桨paddlespeech语音唤醒推理C INT8 定点实现

前面的文章&#xff08;飞桨paddlespeech语音唤醒推理C定点实现&#xff09;讲了INT16的定点实现。因为目前商用的语音唤醒方案推理几乎都是INT8的定点实现&#xff0c;于是我又做了INT8的定点实现。 实现前做了一番调研。量化主要包括权重值量化和激活值量化。权重值由于较小且…
阅读更多...
Log4j2-24-log4j2 相同的日志打印 2 次

Log4j2-24-log4j2 相同的日志打印 2 次

现象 相同的日志打印了两次&#xff0c;且因为日志的配置不同&#xff0c;导致脱敏的情况不一致。 代码与配置 代码 package com.ryo.log4j2.cfg.additivity;import org.apache.logging.log4j.LogManager; import org.apache.logging.log4j.Logger;public class SimpleDemo…
阅读更多...
JNPF低代码平台与其他低代码工具功能有什么不同？

JNPF低代码平台与其他低代码工具功能有什么不同？

JNPF低代码平台是一种新兴的技术解决方案&#xff0c;它可以帮助开发者快速构建应用程序而无需编写大量的代码。本文将深入了解JNPF低代码平台的常见类型与功能特点&#xff0c;帮助读者更好地理解和应用这项技术。 JNPF低代码平台的功能特点。首先&#xff0c;JNPF低代码平台具…
阅读更多...
day28 回溯算法part4

day28 回溯算法part4

93. 复原 IP 地址 中等 有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 ‘.’ 分隔。 例如&#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址&#xff0c;但是 “0.011…
阅读更多...
报错 Cannot read properties of undefined（reading‘addEventListener‘）如何解决

报错 Cannot read properties of undefined（reading‘addEventListener‘）如何解决

我在制作项目中遇到了一个问题&#xff0c;给大家分享一下&#xff0c;如下图&#xff1a; 问题&#xff1a;这是我给一个input输入框绑定的监听事件出现的报错 翻译&#xff1a;无法读取未定义的属性(读取 addEventListener ) 错误原因&#xff1a;js中操作的dom元素的函数方…
阅读更多...
知识库是什么？为什么这么多企业都在用？

知识库是什么？为什么这么多企业都在用？

在信息化的时代&#xff0c;万物互联&#xff0c;企业获取、积累和应用知识的方式也因此发生了巨大的变化。有一项重要工具正是知识库&#xff0c;许多企业和组织都在广泛地使用它。那么&#xff0c;到底什么是知识库&#xff1f;为什么它能受到广泛的接纳和应用呢&#xff1f;…
阅读更多...
MongoDB：从容器使用到 Mongosh、Python/Node.js 数据操作（结构清晰万字长文）

MongoDB：从容器使用到 Mongosh、Python/Node.js 数据操作（结构清晰万字长文）

文章目录 1. 容器与应用之间的关系介绍2. 使用 Docker 容器安装 MongoDB3. Mongosh 操作3.1 Mongosh 连接到 MongoDB3.2 基础操作与 CRUD 4. Python 操作 MongoDB5. Nodejs 操作 MongoDB5.1 Mongodb 和 Mongoose5.2 推荐在项目中使用 Mongoose 参考文献 1. 容器与应用之间的关系…
阅读更多...
数据质量和数据治理的关系 | 京东云技术团队

数据质量和数据治理的关系 | 京东云技术团队

很多不太了解的人会认为&#xff1a;数据治理就是干数据清洗的。 近两年&#xff0c;在我们公司&#xff0c;数据治理团队在数据降本方面做的比较多&#xff0c;效果还不错&#xff0c;我们很多人可能以为&#xff1a;数据治理就是做数据清理的。 在京东科技集团数据治理工作…
阅读更多...
如何使用Docker部署JSON Crack

如何使用Docker部署JSON Crack

文章目录 1. 在Linux上使用Docker安装JSONCrack2. 安装Cpolar内网穿透工具3. 配置JSON Crack界面公网地址4. 远程访问 JSONCrack 界面5. 固定 JSONCrack公网地址 JSON Crack 是一款免费的开源数据可视化应用程序&#xff0c;能够将 JSON、YAML、XML、CSV 等数据格式可视化为交互…
阅读更多...
链接脚本常用命令（KEEP、MEMORY、PROVIDE、ENTRY、AT、ALIGN等）

链接脚本常用命令（KEEP、MEMORY、PROVIDE、ENTRY、AT、ALIGN等）

1、命令介绍 命令作用KEEP保证该段一定在输出文件里&#xff0c;不会被丢弃MEMORY描述目标设备的内存情况&#xff0c;内存分几个区域&#xff0c;每个内存区域的属性PROVIDE从链接脚本导出符号给C语言或者汇编语言使用ENTRY程序入口AT指定段的加载地址ALIGN指定地址的对齐LOA…
阅读更多...
入门产品经理详细教程！PM常用工具|岗位职责|学习书单|能力模型|与项目经理的区别

入门产品经理详细教程！PM常用工具|岗位职责|学习书单|能力模型|与项目经理的区别

移动互联网和AI时代&#xff0c;产品经理无疑是备受瞩目的工作&#xff0c;产品经理负责提出各种创意&#xff0c;同时协调各种资源&#xff0c;推动创意落地实现产品从0到1&#xff0c;而且互联网上对产品经理这个职业也有诸多赞誉—— 产品经理是最接近CEO的岗位产品经理是站…
阅读更多...
解密Sentinel中流控规则的阀值奥秘

解密Sentinel中流控规则的阀值奥秘

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 解密Sentinel中流控规则的阀值奥秘 前言阀值类型基础&#xff1a;Sentinel中的数字量规1. QPS&#xff08;每秒查询率&#xff09;阀值&#xff1a;2. 线程数阀值&#xff1a;3. 关联规则阀值&#xf…
阅读更多...
Java基于SpringBoot的学科竞赛系统，附源码，文档

Java基于SpringBoot的学科竞赛系统，附源码，文档

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…
阅读更多...
【HarmonyOS应用开发】ArkUI 开发框架-基础篇-第一部分（七）

【HarmonyOS应用开发】ArkUI 开发框架-基础篇-第一部分（七）

常用基础组件 一、组件介绍 组件&#xff08;Component&#xff09;是界面搭建与显示的最小单位&#xff0c;HarmonyOS ArkUI声明式开发范式为开发者提供了丰富多样的UI组件&#xff0c;我们可以使用这些组件轻松的编写出更加丰富、漂亮的界面。组件根据功能可以分为以下五大类…
阅读更多...
活动回顾 | 矩阵起源 CEO 王龙：与大数据结合，是大模型成熟的必经之路

活动回顾 | 矩阵起源 CEO 王龙：与大数据结合，是大模型成熟的必经之路

导读 近日&#xff0c;由数据猿和上海大数据联盟主办&#xff0c;上海市经济和信息化委员会、上海市科学技术委员会指导的“第六届金猿季&魔方论坛——大数据产业发展论坛”在上海市四行仓库举行&#xff0c;吸引了数百位业界精英的参与。 本次论坛以“小趋势大未来”为主…
阅读更多...
最新文章

Copyright @ 2022~2023