【算法专题突破】滑动窗口 - 找到字符串中所有字母异位词(14)

简介: 【算法专题突破】滑动窗口 - 找到字符串中所有字母异位词(14)

1. 题目解析

题目链接:438. 找到字符串中所有字母异位词 - 力扣(Leetcode)

这道题很好理解,就是找出从不同位置开始的所有异位词。

2. 算法原理

那我们该如何快速判断是否是异位词呢?

因为异位词的字符种类和数量是一样的,用哈希表就可以很容易的比较。

思路和代码都还是比较简单的:

我们直接维护一个定长的窗口,

然后通过把字符插入哈希计数,然后每走一步判断是否是异位词即可。

3. 代码编写

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> win;
        unordered_map<char, int> cmp;
        vector<int> ans;
        for(auto e : p) cmp[e]++;
        int left = 0, right = 0;
        while(right < s.size()) {
            win[s[right++]]++;
            if(right - left > p.size()) {
                win[s[left]]--;
                if(win[s[left]] == 0) win.erase(s[left]);
                left++;
            }
            if(win == cmp) ans.push_back(left);
        }
        return ans;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

目录
打赏
0
0
0
0
339
分享
相关文章
|
6月前
|
【算法】滑动窗口——最小覆盖子串
【算法】滑动窗口——最小覆盖子串
|
6月前
|
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
4月前
|
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
135 1
两个字符串匹配出最长公共子序列算法
|
4月前
|
条件运算符与条件if的姻缘,打擂台算法和大小写字母转换,if逻辑避坑
条件运算符与条件if的姻缘,打擂台算法和大小写字母转换,if逻辑避坑
44 1
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
【算法】滑动窗口——串联所有单词的子串
【算法】滑动窗口——串联所有单词的子串
|
6月前
|
【算法】滑动窗口——水果成篮
【算法】滑动窗口——水果成篮
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。

热门文章

最新文章