当前位置:网站首页>leetcode-438. 找到字符串中所有字母异位词(滑动窗口)
leetcode-438. 找到字符串中所有字母异位词(滑动窗口)
2022-07-31 05:10:00 【lin钟一】
题目链接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/
思路
方法一:滑动窗口
直接想法
我们需要找到与p字符串的异位词,所以子串的长度与p字符串相同,我们可以用滑动窗口的方法,统计当前子串的字符数量是否可以跟p字符串匹配
算法
- 遍历数组,在滑动中统计窗口每种字符的数量
- 对比s的滑动窗口中的字符数量是否与p字符串中的字符数量相等
代码示例
func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen{
return
}
var mps, mpt [26]int
for i := range p{
mps[s[i] - 'a']++
mpt[p[i] - 'a']++
}
if mps == mpt{
ans = append(ans, 0)
}
for i := range s[:sLen - pLen]{
//维护窗口中所有字符的数量
mps[s[i] - 'a']--
mps[s[i + pLen] - 'a']++
if mps == mpt{
ans = append(ans, i + 1)
}
}
return
}
复杂度分析
- 时间复杂度: O((n - m) * m) 其中n表示s字符串的长度,m表示p字符串的长度,因为一次滑动窗口对比字符数量的时间是O(m),总共滑动n - m次
- 空间复杂度:O(26 * 2) 总共开辟两个26长度的数组
方法二:优化滑动窗口
直接想法
在方法一的基础上,发现我们在每次滑动的时候都要对比字符数量是否相等,极大浪费时间,我们其实可以用一个变量记录每次滑动是改变的字符数量d
算法
- 在方法一的基础上,不用对比字符数量,用d记录滑动窗口中不同字符的数量
- 每次滑动的时候,用d记录是否跟上一次的字符数量不同
- d为0则表示是异位词,记录位置
代码示例
func findAnagrams(s, p string) (ans []int) {
sLen, pLen := len(s), len(p)
if sLen < pLen{
return
}
var mps [26]int
for i := range p{
mps[s[i] - 'a']++
mps[p[i] - 'a']--
}
//记录不同字符的数量
d := 0
for i := range mps{
if mps[i] != 0{
d++
}
}
if d == 0{
ans = append(ans, 0)
}
for i := range s[:sLen - pLen] {
//不同变相同
if mps[s[i] - 'a'] == 1{
d--
//相同变不同
}else if mps[s[i] - 'a'] == 0{
d++
}
mps[s[i] - 'a']--
//不同变相同
if mps[s[i + pLen] - 'a'] == -1{
d--
//相同变不同
}else if mps[s[i + pLen] - 'a'] == 0{
d++
}
mps[s[i + pLen] - 'a']++
if d == 0{
ans = append(ans, i + 1)
}
}
return
}
复杂度分析
- 时间复杂度: O(n) 其中n表示s字符串的长度,遍历p字符串需要O(m)的时间,遍历s字符串需要O(n - m)的时间,刚好加起来是O(n)的时间
- 空间复杂度:O(26) 总共开辟一个26长度的数组
边栏推荐
猜你喜欢
03 【数据代理 事件处理】
MySQL-如何分库分表?一看就懂
有了MVC,为什么还要DDD?
10 【组件编码流程 组件自定义事件 全局事件总线】
MySQL (updating)
Swordsman Offer Special Assault Edition ---- Day 6
The interviewer asked me how to divide the database and the table?Fortunately, I summed up a set of eight-part essays
uni-app进阶之样式框架/生产环境【day10】
Redis Advanced - Cache Issues: Consistency, Penetration, Penetration, Avalanche, Pollution, etc.
第7章 网络层第2次练习题答案(第三版)
随机推荐
Sword Point Offer Special Assault Edition ---- Day 1
太厉害了,终于有人能把文件上传漏洞讲的明明白白了
leetcode-每日一题剑指 Offer II 041. 滑动窗口的平均值(队列模拟)
目标检测学习笔记
With MVC, why DDD?
leetcode-829. 连续整数求和(数论)
Kubernetes 证书可用年限修改
Interviewer, don't ask me to shake hands three times and wave four times again
leetcode-每日一题565. 数组嵌套(标记图和并查集)
11 【定位】
12 【网页布局总结 元素的显示与隐藏】
剑指offer专项突击版 ---- 第 6 天
C语言实验四 循环结构程序设计(一)
MySQL-Explain详解
剑指offer基础版 --- 第24天
Paginate the list collection and display the data on the page
leetcode-每日一题731. 我的日程安排表 II
梳理一下自己常用的快捷键
The process and specific code of sending SMS verification code using flask framework
If the account number or password is entered incorrectly for many times, the account will be banned.