当前位置：首页 > news >正文

【算法学习】-【滑动窗口】-【找到字符串中所有字母异位词】

news 2025/6/28 18:49:57

LeetCode原题链接：438. 找到字符串中所有字母异位词

下面是题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

1、解题思路
前言：如果有第一次学习滑动窗口算法的朋友，可以先阅读一下笔者关于滑动窗口算法的第一篇文章：【算法学习】-【滑动窗口】-【长度最小的子数组】，那里对滑动窗口会有较详细的讲解，下面的解题思路中关于相关算法的步骤就仅进行简单的叙述啦。

由题目描述可得，本题主要可分为以下两个步骤：
（1）判断一个字符串是否为另一个字符串的异位词
这里需要借助哈希表这个数据结构来进行判断，即将两个字符串中的字符分别放入两个哈希表中，然后对比这两个哈希表，若两个哈希表中的字符及字符个数都一样，则说明是异位词；否则不是。

（2）确定滑动窗口
相较于之前笔者有关滑动窗口算法的文章中的滑动窗口，这里的窗口大小是恒定的，即用于构成窗口大小的两个指针是 “共进退” 的。故此时直接照搬之前控制窗口移动的思路反而会使情况变得复杂。下面介绍一下算法的步骤：

先初始化两个哈希表，便于直接进行第一次判断
判断两个哈希表中的内容否相等，若相等，则记录索引（也就是构成窗口的前面的那个指针的值）
接着无论是否相等都需将字符串s对应的哈希表中的第一个字符删除（注意这里要先让数量--，数量为0后才执行删除操作）而进行下一次枚举
删除后，向s对应的哈希表中插入新的字符，然后两个指针都向后移动一位，准备进行下一次的判断。循环执行上述过程。

2、具体代码

 	vector<int> findAnagrams(string s, string p){unordered_map<char, int> mapOfp;unordered_map<char, int> mapOfs;//初始化哈希表for (size_t i = 0; i < p.size(); i++){mapOfp[p[i]]++;mapOfs[s[i]]++;}vector<int> res;size_t cur = p.size();size_t begin = 0;while (cur <= s.size()){if (mapOfp == mapOfs){res.push_back(begin);}if( --mapOfs[s[begin]] == 0){mapOfs.erase(s[begin]);}begin++;mapOfs[s[cur++]]++;}if (mapOfp == mapOfs){res.push_back(begin);}return res;}