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

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

一、题目描述：

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

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

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

分析

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

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

P = cac

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

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

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

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

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

看了上述例证之后，我们就能够明白，包含 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
}

四、总结：

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

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

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

欢迎点赞，关注，收藏

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

好了，本次就到这里

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

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