【刷题日记】467. 环绕字符串中唯一的子字符串

简介: 本次刷题日记的第 49 篇,力扣题为:467. 环绕字符串中唯一的子字符串,中等

本次刷题日记的第 49 篇,力扣题为:467. 环绕字符串中唯一的子字符串中等

一、题目描述:

image.png

环绕字符串中唯一的子字符串, 这里我们可以仔细查看一下题目中给出来的示例

二、这道题考察了什么思想?你的思路是什么?

题目给出的比较明确,给出了 p 字符串,第一我们需要找到 p 字符串中的子串,第二,我们需要计算这些字符串中,有哪一些是可以放在 一个 无线环绕的字符串(za...za...za...za...za....) 中找到的字符串

分析

也就是说,既是 p 的子串,又是 s 的子串,且 非空

首先我们来仔细查看一下示例

P = cac

我们可以知道,字串有 c, a, ca, ac,cac****

但是将这些子串放到 s 无线环绕字符串中查找的时候,只有 c, a 是满足 s 子串的,因此 这种情况,满足条件的字串只有 2 个

image.png

图中 p = abc ,对应的子串就有 6 个,分别是从 a 推导到 c,得到的这些字符串都是可以在无线环绕字符串中找到的

那么我们可以这样来玩,定义一个数组 dp,下标为字符索引,由于字母是 26 个字母,则下标范围是 0 - 25, 那么上述例子我们就可以看到应该是这样的效果

image.png

那么还是同样的方式,我们来看看下面这样的字符串呢?

image.png

看了上述例证之后,我们就能够明白,包含 c 的子串如果有 3 个话,那么 p 中一定包含 abc ,如果 包含 c 的子串有 2 个话,那么一定包含 bc

另外

因为我们是在无线环绕的字符串中查找子串,因此我们需要考虑 za... 的情况,做法也是一样,处理相邻,我们是校验当前字母和上一个字母是否差 1 ,这里我们需要注意,当前字母与上一个字母相差 25 也是满足条件的

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码,这里需要注意

  • 字符之差为 1 或 -25 都是可以考虑计算的,因为题目中给出的无线环绕字符串是 za...za...za..z.a...za...
  • 因此不仅要考虑 p 的相邻字母是否差 1 ,还要考虑是否是 za 的情况

编码如下:

func findSubstringInWraproundString(p string) (ans int) {
    help:= [26]int{}
    k := 0
    for i, ch := range p {
         // 字符之差为 1 或 -25,因为题目中给出的无线环绕字符串是 za...za...za..z.a...za...
         // 因此不仅要考虑 p 的相邻字母是否差 1 ,还要考虑是否是 za 的情况
        if i > 0 && (byte(ch)-p[i-1]+26)%26 == 1 {
            k++
        } else {
            k = 1
        }
        help[ch-'a'] = max(help[ch-'a'], k)
    }
    for _, v := range help{
        ans += v
    }
    return
}
func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

四、总结:

image.png

此处咱们遍历了一次 p 和 help,时间复杂度为 O(n) ,空间复杂度为 O(∑),我们引入了 help[26] 数组 的空间消耗,∑ 为 26

原题地址:467. 环绕字符串中唯一的子字符串

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~


相关文章
|
5月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【动态规划刷题 12】单词拆分 && 环绕字符串中唯一的子字符串
【动态规划刷题 12】单词拆分 && 环绕字符串中唯一的子字符串
|
6月前
|
存储 算法 索引
刷题专栏(二十六):字符串中的第一个唯一字符
刷题专栏(二十六):字符串中的第一个唯一字符
100 1
刷题专栏(二十六):字符串中的第一个唯一字符
|
Cloud Native
【刷题日记】316. 去除重复字母
本次刷题日记的第 42 篇,力扣题为:316. 去除重复字母 ,中等
|
Cloud Native
【刷题日记】30. 串联所有单词的子串
本次刷题日记的第 75篇,力扣题为:30. 串联所有单词的子串 ,困难
|
6月前
|
算法 Java
刷题专栏(二十九):重复的子字符串
刷题专栏(二十九):重复的子字符串
133 2
|
6月前
|
Java
每日一刷《剑指offer》字符串篇之正则表达式匹配
每日一刷《剑指offer》字符串篇之正则表达式匹配
72 0
每日一刷《剑指offer》字符串篇之正则表达式匹配
|
6月前
|
机器人 Java
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
70 0
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
|
6月前
|
算法
六六力扣刷题字符串之重复的子字符串
六六力扣刷题字符串之重复的子字符串
64 0
|
算法 索引
代码随想录算法训练营第九天 | LeetCode 8. 找出字符串中第一个匹配项的下标、LeetCode 459. 重复的子字符串
代码随想录算法训练营第九天 | LeetCode 8. 找出字符串中第一个匹配项的下标、LeetCode 459. 重复的子字符串
37 0