【LeetCode刷题记录】438. 找到字符串中所有字母异位词

本文主要是介绍【LeetCode刷题记录】438. 找到字符串中所有字母异位词，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 <= s.length, p.length <= 3 * 10^4$
s 和 p 仅包含小写字母

思路

本题采用滑动窗口思想。首先需要考虑字符串s和p的长度，如果p的长度大于s则直接返回空数组。由于s和p仅包含小写字母，可利用哈希表存储每个字符出现次数，遍历滑动窗口中每个字符出现次数，与p字符串中的字符出现次数进行比较即可。
采用vector可直接进行数组比较。
将s第一个子串与p进行比较需要单独讨论。
下面是字符串s滑动窗口字符计数情况展示：
在这里插入图片描述

代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> v;int ns = s.length(), np = p.length();vector<int> sCnt(26);vector<int> pCnt(26);if (ns < np)return v;for (int i = 0; i < np; i++) {pCnt[p[i] - 'a']++;sCnt[s[i] - 'a']++;}if (sCnt == pCnt) {v.push_back(0);}for (int i = 0; i < ns - np; i++) {sCnt[s[i] - 'a']--;sCnt[s[i + np] - 'a']++;if (sCnt == pCnt) {v.push_back(i + 1);}}return v;}
};