113 lines
3.9 KiB
JavaScript
113 lines
3.9 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/find-all-anagrams-in-a-string/
|
||
* @param {string} s
|
||
* @param {string} p
|
||
* @return {number[]}
|
||
*/
|
||
const findAnagrams = function (s, p) {
|
||
|
||
};
|
||
|
||
/*
|
||
按照暴力解法的话我们可能会把p的所有异位词都枚举出来，之后遍历遍历所有的异位词，利用indexof查看每一个异位词在s中的位置，如果
|
||
这个异位词在s中存在，那么就把起始下标放入到结果集中，如果p非常长的话那么所有异位词就是一个长度的全排列!m,加上对s的查找，那就是一个
|
||
(n+m)*!m, 这显然是不能接受的，所以我们需要换一种思路.
|
||
思路：异位词和原词在单词数量上是一致的，所以我们可以维护一个在s上，长度位p.length的窗口，只要这个窗口里面所有单词出现的数量和
|
||
p中所有单词出现的数量一致的话，那么就认为这个窗口表示的单词是p的一个异位词，最后只需把窗口的起始下标放入结果集合即可
|
||
*/
|
||
function f1(s, p) {
|
||
const result = []; // 返回的结果集
|
||
if (s.length < p.length) return result; // p比s还长，在s中不可能有p的异位词，直接返回
|
||
const need = new Map(); // 记录p中每一个词出现的次数，用于验证异位词
|
||
const window = new Map(); // 记录当前窗口中的异位词
|
||
// 统计p的所有字符出现的次数
|
||
for (const char of p) {
|
||
need.set(char, (need.get(char) || 0) + 1);
|
||
}
|
||
|
||
let left = 0; // 滑动窗口的左边界
|
||
let right = 0; // 滑动窗口的右边界
|
||
let valid = 0; // 滑动窗口中符合异位字的字符数量;
|
||
|
||
while (right < s.length) {
|
||
const char = s[right];
|
||
if (need.has(char)) {
|
||
window.set(char, (window.get(char) || 0) + 1);
|
||
if (window.get(char) === need.get(char)) {
|
||
valid++;
|
||
}
|
||
}
|
||
|
||
// 如果窗口长度等于异位字符p的长度，那么就检测当前窗口是否是一个异位词
|
||
if (right - left + 1 === p.length) {
|
||
if (valid === need.size) {
|
||
result.push(left); // 把left添加到结果集中
|
||
}
|
||
const leftChar = s[left];
|
||
// 收缩窗口
|
||
left++;
|
||
// 判断收缩掉的这个字符是否是need中的某一个字符
|
||
if (need.has(leftChar)) {
|
||
if (window.get(leftChar) === need.get(leftChar)) {
|
||
valid--; // 验证符合异位词字符个数的词减1
|
||
}
|
||
window.set(leftChar, window.get(leftChar) - 1); // 使这个字符的数量减1
|
||
}
|
||
}
|
||
// 扩展窗口
|
||
right++;
|
||
}
|
||
return result;
|
||
}
|
||
|
||
function f3(s, p) {
|
||
const result = []; // 返回的结果集
|
||
if (s.length < p.length) return result; // p比s还长，在s中不可能有p的异位词，直接返回
|
||
|
||
const need = new Map(); // 记录p中每一个字符出现的次数，用于验证异位词
|
||
const window = new Map(); // 记录当前窗口中的异位词
|
||
|
||
// 统计p的所有字符出现的次数
|
||
for (const char of p) {
|
||
need.set(char, (need.get(char) || 0) + 1);
|
||
}
|
||
|
||
let left = 0; // 滑动窗口的左边界
|
||
let right = 0; // 滑动窗口的右边界
|
||
|
||
while (right < s.length) {
|
||
const char = s[right];
|
||
// 扩展窗口
|
||
window.set(char, (window.get(char) || 0) + 1);
|
||
|
||
// 如果当前窗口大小达到p的长度，判断是否为异位词
|
||
if (right - left + 1 === p.length) {
|
||
// 比较窗口内字符的频次是否和p中一致
|
||
let isAnagram = true;
|
||
for (const [key, value] of need) {
|
||
if (window.get(key) !== value) {
|
||
isAnagram = false;
|
||
break;
|
||
}
|
||
}
|
||
|
||
if (isAnagram) {
|
||
result.push(left); // 将符合条件的起始索引加入结果
|
||
}
|
||
|
||
// 收缩窗口
|
||
const leftChar = s[left];
|
||
window.set(leftChar, window.get(leftChar) - 1); // 减少左边字符的频次
|
||
if (window.get(leftChar) === 0) {
|
||
window.delete(leftChar); // 如果频次为0，移除该字符
|
||
}
|
||
left++; // 移动左指针
|
||
}
|
||
|
||
// 扩展右指针
|
||
right++;
|
||
}
|
||
|
||
return result;
|
||
}
|