2023-02-05.md

题目

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p'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.

思路

代码

// runtime 90.77% memory 93.80%
var findAnagrams = function(s, p) {
  const len_s = s.length
  const len_p = p.length
  const freq_p = Array(26).fill(0)
  const freq_w = Array(26).fill(0)
  const ans = []
  if (len_s < len_p) {
    return []
  }
  for (let i = 0; i < len_p; i++) {
    freq_p[p.charCodeAt(i)-97]++
    freq_w[s.charCodeAt(i)-97]++
  }
  if (isEqual(freq_p, freq_w)) {
    ans.push(0)
  }
  for (let i = len_p; i < len_s; i++) {
    freq_w[s.charCodeAt(i-len_p)-97]--
    freq_w[s.charCodeAt(i)-97]++
    if (isEqual(freq_p, freq_w)) {
      ans.push(i-len_p+1)
    }
  }
  return ans
}
function isEqual(array1, array2) {
  return array1.length === array2.length && array1.every((value, index) => value === array2[index])
}