本次刷题日记的第 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. 环绕字符串中唯一的子字符串
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~