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 * 104
• s 和 p 仅包含小写字母

通过次数 107,426
提交次数 205,210

思路

滑动窗口，判断其中的元素是否都一致即可。用数组或者哈希表的方式计数。

解答

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  if (s.length < p.length) return [];
  const res = [];
  const sArr = new Array(26).fill(0);
  const pArr = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    const sp = p[i];
    const ss = s[i];
    sArr[ss.charCodeAt() - 97]++;
    pArr[sp.charCodeAt() - 97]++;
  }
  const pStr = pArr.toString();
  if (sArr.toString() === pStr) res.push(0);
  for (let i = 1; i <= s.length - p.length; i++) {
    const ss = s[i - 1];
    const ss1 = s[i - 1 + p.length];

    sArr[ss.charCodeAt() - 97]--;
    sArr[ss1.charCodeAt() - 97]++;
    if (sArr.toString() === pStr) res.push(i);
  }
  return res;
};