1、题目
给定两个字符串 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 * 104s和p仅包含小写字母
2、题解
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>438. 找到字符串中所有字母异位词</title>
</head>
<body>
<script>
var findAnagrams = function (s, p) {
const len = s.length || 0;
const plen = p.length || 0;
const count = Array(26).fill(0);
const aCharCode = "a".charCodeAt();
const result = [];
// 根据p设置初始计数值
[...p].forEach((char) => {
count[char.charCodeAt() - aCharCode]++;
});
console.log("初始化计数:", count);
let startIndex = 0;
for (let i = 0; i < len; i++) {
let currentChar = s[i];
let currentCharCode = currentChar.charCodeAt() - aCharCode;
count[currentCharCode]--;
//如果窗口大小等于p大小,验证是否异构词
if (i - startIndex + 1 === plen) {
//count是"平"的说明异构词产生,如果有值大于0,说明异构词不完整,如果有值小于0说明子字符串中含有p中不包含的字符
if (count.every((num) => num === 0)) {
result.push(startIndex);
}
count[s[startIndex].charCodeAt() - aCharCode]++;
startIndex++;
}
}
return result;
};
document.write(findAnagrams("cbaebabacd", "abc"));
</script>
</body>
</html>
这段代码是解决“找到字符串中所有字母异位词”的一个示例实现。字母异位词指的是由相同字母以不同顺序构成的单词或短语。在这个问题中，给定两个字符串 s 和 p，需要在 s 中找出所有 p 的异位词的起始索引。这个解法使用了滑动窗口和字符计数的方法来实现。
3、解题思路详解：
- 初始化字符计数器：首先，创建一个长度为 26 的数组
count（因为英文字母一共有26个），用于跟踪p中每个字符的出现次数。初始化时，遍历字符串p，每出现一个字符，就在对应的位置（根据字母的 ASCII 码计算得出）上加一。 - **遍历字符串
s**：接着，开始遍历字符串s。对于字符串s中的每个字符，都减少count数组对应位置上的计数，表示这个字符在当前考虑的窗口中被使用了一次。 - 检查窗口大小：如果当前窗口大小（即考虑中的子字符串长度）等于字符串
p的长度，那么检查count数组。 - 判断是否字母异位词：如果
count数组的所有元素都为 0，说明当前窗口包含的字符与p中的字符完全一致（每个字符出现的次数相同），即找到了一个字母异位词。此时，将当前窗口的起始索引startIndex添加到结果数组result中。 - 滑动窗口：为了继续寻找下一个可能的异位词，将窗口向右滑动一位。即增加窗口起始位置字符的计数（意味着将其从当前考虑的窗口中移除），然后增加
startIndex（窗口起始索引）。 - 重复上述过程，直至遍历完字符串
s。 - 返回结果：返回结果数组
result，包含了所有在字符串s中找到的字符串p的字母异位词的起始索引。
这种方法的优势在于，通过维护一个固定长度的滑动窗口以及对应的字符计数器，我们能够以线性时间复杂度遍历一次字符串 s 来找出所有符合条件的异位词起始索引，从而实现高效解题。
4、算法评价
此算法的复杂度分析：
- 时间复杂度：
- 初始化统计数组
count时，遍历了一次字符串p，时间复杂度为 O(m)，其中 m 是字符串p的长度。 - 遍历字符串
s时，对每个字符的处理是常数时间复杂度，时间复杂度为 O(n)，其中 n 是字符串s的长度。 - 在每个滑动窗口中检查是否所有字符计数减为 0 的操作是常数时间复杂度，因为
count数组的大小固定为 26（英文小写字母的数量），所以与n或m的长度无关。
因此，总的时间复杂度是 O(m + n)。
- 初始化统计数组
- 空间复杂度：
- 空间复杂度主要取决于统计数组
count，其大小固定为 26（对于英文小写字母）。其它变量使用的空间是常数级别的。 - 结果数组
result的空间大小最大为 O(n)，因为理论上字符串s每个字符都有可能是异位词的起始位置。
因此，总的空间复杂度是 O(1)。现实中，因为要存储结果所以算法实际占用的空间可能接近 O(n)，但是 O(1) 表示除了输入和输出以外，额外空间是恒定的。 - 空间复杂度主要取决于统计数组
综上所述，此算法是线性的，即它可以在与输入字符串长度成比例的时间内完成处理，且需要的额外空间是固定的。这使得算法非常适用于处理大规模的数据。