Leetcode刷题详解——环绕字符串中唯一的子字符串

2023-12-09 09:01

本文主要是介绍Leetcode刷题详解——环绕字符串中唯一的子字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 题目链接:467. 环绕字符串中唯一的子字符串

2. 题目描述:

定义字符串 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 <= 105
  • s 由小写英文字母组成

3. 解法(动态规划):

3.1 算法思路:

1. 状态表示:

dp[i]表示:以 i位置的元素为结尾的所有子串里面,有多少个在 base中出现过

2. 状态转移方程:

对于 dp[i],我们可以根据子串的长度划分为两类:

  1. 子串的长度等于1:此时这一个字符会出现在 base
  2. 子串的长度大于1:如果 i位置的字符和 i-1位置上的字符组合后,出现在 base中的话,那么 dp[i-1]里面的所有子串后面填上一个 s[i]依旧在 base中出现,因此 dp[i]=dp[i-1]

综上,dp[i]=1+dp[i-1],其中 dp[i-1]是否加上需要先做一下判断

3. 初始化:

将表里面的值都初始化为1

4. 填表顺序:

从左往右

5. 返回值:

这里不能直接返回 dp表里面的和,因为会又重复的结果。在返回之前,我们需要先去重:

  1. 相同字符结尾的 dp值,我们仅需要保留最大的即可,其余 dp值对应的子串都可以在最大的里面找到
  2. 可以创建一个大小为26的数组,统计所有字符结尾的最大 dp
  3. 最后返回数组中所有元素的和即可

3.2 C++算法代码:

class Solution {
public:int findSubstringInWraproundString(string s) {// 获取字符串长度int n = s.size();// 初始化动态规划数组,dp[i]表示以第i个字符结尾的最长连续子串的长度vector<int> dp(n, 1);// 遍历字符串,从第二个字符开始for (int i = 1; i < n; i++) {// 如果当前字符与前一个字符相差1或者当前字符是'z'且前一个字符是'a',则说明可以组成连续子串if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a')) {// 更新dp数组dp[i] = dp[i - 1] + 1;}}// 初始化哈希数组,用于记录每个字符作为子串末尾时的最大长度int hash[26] = {0};// 遍历dp数组,更新哈希数组for (int i = 0; i < n; i++) {hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}// 计算所有子串长度之和int sum = 0;for (auto x : hash) sum += x;return sum;}
};

这篇关于Leetcode刷题详解——环绕字符串中唯一的子字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/473210

相关文章

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

Mysql 中的多表连接和连接类型详解

《Mysql中的多表连接和连接类型详解》这篇文章详细介绍了MySQL中的多表连接及其各种类型,包括内连接、左连接、右连接、全外连接、自连接和交叉连接,通过这些连接方式,可以将分散在不同表中的相关数据... 目录什么是多表连接?1. 内连接(INNER JOIN)2. 左连接(LEFT JOIN 或 LEFT

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》:本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者

Linux内核之内核裁剪详解

《Linux内核之内核裁剪详解》Linux内核裁剪是通过移除不必要的功能和模块,调整配置参数来优化内核,以满足特定需求,裁剪的方法包括使用配置选项、模块化设计和优化配置参数,图形裁剪工具如makeme... 目录简介一、 裁剪的原因二、裁剪的方法三、图形裁剪工具四、操作说明五、make menuconfig

详解Java中的敏感信息处理

《详解Java中的敏感信息处理》平时开发中常常会遇到像用户的手机号、姓名、身份证等敏感信息需要处理,这篇文章主要为大家整理了一些常用的方法,希望对大家有所帮助... 目录前后端传输AES 对称加密RSA 非对称加密混合加密数据库加密MD5 + Salt/SHA + SaltAES 加密平时开发中遇到像用户的

Springboot使用RabbitMQ实现关闭超时订单(示例详解)

《Springboot使用RabbitMQ实现关闭超时订单(示例详解)》介绍了如何在SpringBoot项目中使用RabbitMQ实现订单的延时处理和超时关闭,通过配置RabbitMQ的交换机、队列和... 目录1.maven中引入rabbitmq的依赖:2.application.yml中进行rabbit

C语言线程池的常见实现方式详解

《C语言线程池的常见实现方式详解》本文介绍了如何使用C语言实现一个基本的线程池,线程池的实现包括工作线程、任务队列、任务调度、线程池的初始化、任务添加、销毁等步骤,感兴趣的朋友跟随小编一起看看吧... 目录1. 线程池的基本结构2. 线程池的实现步骤3. 线程池的核心数据结构4. 线程池的详细实现4.1 初

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.

SpringBoot使用Apache POI库读取Excel文件的操作详解

《SpringBoot使用ApachePOI库读取Excel文件的操作详解》在日常开发中,我们经常需要处理Excel文件中的数据,无论是从数据库导入数据、处理数据报表,还是批量生成数据,都可能会遇到... 目录项目背景依赖导入读取Excel模板的实现代码实现代码解析ExcelDemoInfoDTO 数据传输