438. Find All Anagrams in a String
438. Find All Anagrams in a String
题目
Given two strings s and p, return an array of all the start indices ofp _' s anagrams in _s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Constraints:
1 <= s.length, p.length <= 3 * 10^4sandpconsist of lowercase English letters.
题目大意
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
解题思路
使用滑动窗口算法，思路如下：
- 使用双指针中的左右指针，初始化
left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」； - 不断地增加
right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了s1.length个字符）； - 停止增加
right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含s1.length个字符了）；同时，每次增加left，都要更新一轮结果； - 重复第 2 和第 3 步，直到
right到达字符串s2的尽头；
详细的滑动窗口答题框架讲解，可阅读 《3.11 滑动窗口》。
代码
/**
* @param {string} s
* @param {string} p
* @return {number[]}
*/
var findAnagrams = function (s, p) {
let window = {},
need = {};
for (let i of p) {
need[i] = (need[i] || 0) + 1;
}
let left = 0,
right = 0,
valid = 0,
// 记录结果
res = [];
while (right < s.length) {
let c = s[right];
right++;
// 进行窗口内数据的一系列更新
if (need[c]) {
window[c] = (window[c] || 0) + 1;
if (window[c] == need[c]) {
valid++;
}
}
// 判断左侧窗口是否要收缩
if (right - left == p.length) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == Object.keys(need).length) {
res.push(left);
}
let d = s[left];
left++;
// 进行窗口内数据的一系列更新
if (need[d]) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return res;
};