「动态规划」如何求环绕字符串中唯一的子字符串个数?

467. 环绕字符串中唯一的子字符串icon-default.png?t=N7T8https://leetcode.cn/problems/unique-substrings-in-wraparound-string/description/

定义字符串base为一个"abcdefghijklmnopqrstuvwxyz"无限环绕的字符串,所以base看起来是这样的:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."。给你一个字符串s,请你统计并返回s中有多少不同非空子串也在base中出现。

  1. 输入:s = "a",输出:1,解释:字符串s的子字符串"a"在base中出现。
  2. 输入:s = "cac",输出:2,解释:字符串s有两个子字符串("a", "c")在base中出现。
  3. 输入:s = "zab",输出:6,解释:字符串s有六个子字符串("z", "a", "b", "za", "ab", and "zab")在base中出现。

提示:1 <= s.length <= 10^5,s由小写英文字母组成。


我们用动态规划的思想来解决这个问题。

确定状态表示:根据经验和题目要求,我们用dp[i]表示:以i位置为结尾的所有子串中,有几个在base中出现

推导状态转移方程:由于题目描述中说明,s由小写英文字母组成,所以以i位置为结尾的子串,如果长度是1,那么一定在base中出现。如果以i位置为结尾的子串的长度大于1,那么一定是以i - 1位置为结尾的子串拼接上s[i]。如果s[i] == s[i - 1] + 1,或者s[i - 1] == 'z' && s[i] == 'a',那么以i - 1位置为结尾的所有在base中出现的子串,在后面拼接上s[i]后,一定也在base中出现,这样的子串有dp[i - 1]个。

初始化:根据状态转移方程,注意到当i = 0时,判断s[i] == s[i - 1] + 1时会越界。所以需要初始化dp[0]的值,根据状态表示,显然dp[0] = 1。当然,我们可以把dp表的所有值都初始化为1,计算dp[i](i > 0)时,如果s[i] == s[i - 1] + 1,或者s[i - 1] == 'z' && s[i] == 'a',那么dp[i] += dp[i - 1]

填表顺序:根据状态转移方程,显然应从左往右填表

返回值:根据状态表示,我们不能简单地返回dp表所有值的和,因为有些情况是重复的。我们需要考虑如何去重。注意到,相同字符结尾的dp值,我们只需要保留最大的,因为其余dp值对应的子串都可以在最大的dp值对应的子串中找到。比如,2个子串的结尾都是'c',其中一个dp值是3,那么出现在base中的子串就是("c", "bc", "abc"),另一个dp值是5,那么出现在base中的子串就是("c", "bc", "abc", "zabc", "yzabc"),显然后者包含前者。如何做到这一点呢?我们只需要定义一个哈希表,把每个字符对应的最大dp值存储到对应的位置即可。

细节问题:dp表的规模和s相同,均为1 x n

class Solution {
public:int findSubstringInWraproundString(string s) {int n = s.size();// 创建dp表vector<int> dp(n, 1);// 填表for (int i = 1; i < n; i++) {if (s[i] == s[i - 1] + 1 || (s[i - 1] == 'z' && s[i] == 'a')) {dp[i] += dp[i - 1];}}// 相同字符结尾的dp值,只保留最大的vector<int> hash(26);for (int i = 0; i < n; i++) {hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}return accumulate(hash.begin(), hash.end(), 0);}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

服务器数据恢复—raid5热备盘同步失败导致阵列崩溃如何恢复数据?

服务器存储数据恢复环境&故障&#xff1a; 某品牌DS5300存储&#xff0c;包含一个存储机头和多个磁盘柜&#xff0c;组建了多组RAID5磁盘阵列。 某个磁盘柜中的一组RAID5阵列由15块数据盘和1块热备硬盘组建。该磁盘柜中的某块硬盘离线&#xff0c;热备盘自动替换并开始同步…

Linux 7种 进程间通信方式

传统进程间通信 通过文件实现进程间通信 必须人为保证先后顺序 A--->硬盘---> B&#xff08;B不知道A什么时候把内容传到硬盘中&#xff09; 1.无名管道 2.有名管道 3.信号 IPC进程间通信 4.消息队列 5.共享内存 6.信号灯集 7.socket通信 一、无名管道&a…

【c2】编译预处理,gdb,makefile,文件,多线程,动静态库

文章目录 1.编译预处理&#xff1a;C源程序 - 编译预处理【#开头指令和特殊符号进行处理&#xff0c;删除程序中注释和多余空白行】- 编译2.gdb调试&#xff1a;多进/线程中无法用3.makefile文件&#xff1a;make是一个解释makefile中指令的命令工具4.文件&#xff1a;fprint/f…

Flink Sql Redis Connector

经常做开发的小伙伴肯定知道用flink连接redis的时候比较麻烦&#xff0c;更麻烦的是解析redis数据&#xff0c;如果rdis可以普通数据库那样用flink sql连接并且数据可以像表格那样展示出来就会非常方便。 历时多天&#xff0c;我终于把flink sql redis connector写出来了&…

预备资金有5000-6000买什么电脑比较好?大学生电脑选购指南

小新pro14 2024 处理器&#xff1a;采用了英特尔酷睿Ultra5 125H或Ultra9 185H两种处理器可选&#xff0c;这是英特尔最新的高性能低功耗处理器&#xff0c;具有18个线程&#xff0c;最高可达4.5GHz的加速频率&#xff0c;支持PCIe 4.0接口&#xff0c;内置了强大的ARC核芯显卡…

Pwn刷题记录(不停更新)

1、CTFshow-pwn04&#xff08;基础canary&#xff09; ​ 好久没碰过pwn了&#xff0c;今天临时做一道吧&#xff0c;毕竟刚联合了WSL和VSCode&#xff0c;想着试着做一道题看看&#xff0c;结果随手一点&#xff0c;就是一个很少接触的&#xff0c;拿来刷刷&#xff1a; ​ …

在SQL中使用explode函数展开数组的详细指南

目录 简介示例1&#xff1a;简单数组展开示例2&#xff1a;展开嵌套数组示例3&#xff1a;与其他函数结合使用处理结构体数组示例&#xff1a;展开包含结构体的数组示例2&#xff1a;展开嵌套结构体数组 总结 简介 在处理SQL中的数组数据时&#xff0c;explode函数非常有用。它…

吴恩达机器学习 第二课 week4 决策树

目录 01 学习目标 02 实现工具 03 问题描述 04 构建决策树 05 总结 01 学习目标 &#xff08;1&#xff09;理解“熵”、“交叉熵&#xff08;信息增益&#xff09;”的概念 &#xff08;2&#xff09;掌握决策树的构建步骤与要点 02 实现工具 &#xff08;1&#xff09;…

Web框架简介

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 如果你要从零开始建立了一些网站&#xff0c;可能会注意到你不得不反复解决一些类似的问题。这样做是令人厌烦的&#xff0c;并且违反了良好编程的核…

kotlin集合框架

1、集合框架的接口类型对比 2、不可变和可变List fun main() {// 不可变List - 不能删除或添加元素val intList: List<Int> listOf(1,2,3)intList.forEach{println(it) // 1 2 3}println("")// 可变List - 可以删除或添加元素val mutableList mutableListO…

展示3D模型的网站哪个好?

如果仅仅是模型展示&#xff0c;目前国内外值得推荐的无非就是那么几个&#xff0c;它们各自有不同的特点和优势&#xff1a; 1、Sketchfab&#xff1a;Sketchfab是一个知名的3D模型展示平台&#xff0c;提供了海量的模型资源和出色的3D展示效果。用户无需安装任何插件即可在线…

移动Web开发实战内容要点!!!

移动web开发 目录 移动web开发 第一章、Web开发标准与网页网站制作介绍 1.1Web开发标准 1.2网页基本构成元素 第二章、Web开发技术基础 2.1HTML的主要特点&#xff1a; 2.2HTML基本知识 2.3CSS样式 2.4JavaScript 第三章、打造移动Web应用程序 3.1为什么Android会成…

学生课程信息管理系统

摘 要 目前&#xff0c;随着科学经济的不断发展&#xff0c;高校规模不断扩大&#xff0c;所招收的学生人数越来越 多&#xff1b;所开设的课程也越来越多。随之而来的是高校需要管理更多的事务。对于日益增 长的学生相关专业的课程也在不断增多&#xff0c;高校对其管理具有一…

51单片机STC89C52RC——2.3 两个独立按键模拟控制LED流水灯方向

目的 按下K1键LED流水向左移动 按下K2键LED流水向右移动 一&#xff0c;STC单片机模块 二&#xff0c;独立按键 2.1 独立按键位置 2.2 独立按键电路图 这里要注意一个设计的bug P3_1 引脚对应是K1 P3_0 引脚对应是K2 要实现按一下点亮、再按一下熄灭&#xff0c;我们就需…

空间复杂度 线性表,顺序表尾插。

各位少年&#xff0c;大家好&#xff0c;我是那一脸阳光&#xff0c;本次分享的主题是时间复杂度和空间复杂度 还有顺序表文章讲解和分享&#xff0c;如有不对可以评论区指导。 时间复杂度例题 // 计算斐波那契递归Fib的时间复杂度&#xff1f; long long Fib(size_t N){if(N…

docker将容器打包提交为镜像,再打包成tar包

将容器打包成镜像可以通过以下步骤来实现。这里以 Docker 为例&#xff0c;假设你已经安装了 Docker 并且有一个正在运行的容器。 1. 找到正在运行的容器 首先&#xff0c;你需要找到你想要打包成镜像的容器的 ID 或者名字。可以使用以下命令查看所有正在运行的容器&#xff…

Leetcode3185. 构成整天的下标对数目 II

Every day a Leetcode 题目来源&#xff1a;3185. 构成整天的下标对数目 II 解法1&#xff1a;哈希 本质思路类同经典的“两数之和”。枚举右&#xff0c;用哈希表维护左。 枚举 j&#xff0c;并维护 cnt[x] 表示所有满足 i < j 的下标 i 中&#xff0c;有几个 hours[i]…

常见的LED显示屏拼接优缺点解析

LED显示屏拼接技术在现代显示技术中占据了重要地位。随着市场需求的不断增长&#xff0c;各种拼接屏技术也不断发展&#xff0c;每种技术都有其独特的优势和不足。本文将详细解析常见的几种拼接屏技术&#xff0c;包括LED显示屏拼接、投影DLP拼接和等离子PDP拼接。 LED显示屏拼…

【HTTPS云证书部署】SpingBoot部署证书

这里以华为云证书为例。 1. 下载证书 2. 解压 3. 选择.top_Tomcat复制到SpringBoot的Resource/source下 4. 在.properties文件中进行配置 修改key-store和key-store-password

实验室自用LabVIEW软件与商用软件价格差异分析

实验室自用LabVIEW软件与商用软件在价格上的差异源于功能与扩展包、技术支持与服务、使用场景与合规性、更新与维护、市场与定价策略、培训与教育资源及许可证管理与合规审计等方面的不同。商用软件提供更全面的功能和支持&#xff0c;确保高可靠性和合规性&#xff0c;因此价格…