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 仅包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string

javascript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
  const res = []
  const pMap = new Map()
  
  for (let i = 0; i < p.length;i++){
    pMap.set(p[i], (pMap.get(p[i]) || 0) + 1)
  }
  
  for (let i = 0; i <= s.length - p.length; i++) {
    let flag = true
    const sMap = new Map()
    for (let j = 0; j < p.length; j++) {
      const letter = s[i + j]
      sMap.set(letter, (sMap.get(letter) || 0) + 1)
      if (sMap.get(letter) > pMap.get(letter) || !pMap.has(letter)) {
        flag = false
        break
      }
    }
    if(flag){
      res.push(i)
    }
  }

  return res
}

var findAnagrams = function(s, p) {
  const res = []
  const pMap = new Map()

  for (let j = 0; j < p.length;j++){
    pMap.set(s[j], (pMap.get(s[j]) || 0) + 1)
  }

  for (let j = 0; j < p.length;j++){
    pMap.set(p[j], (pMap.get(p[j]) || 0) - 1)
    if(pMap.get(p[j]) === 0){
      pMap.delete(p[j])
    }
  }

  for (let j = 0; j <= s.length - p.length; j++) {
    if(j > 0){
      const nextLetter = s[j + p.length - 1]
      pMap.set(nextLetter, (pMap.get(nextLetter) || 0) + 1)
      if(pMap.get(nextLetter) === 0){
        pMap.delete(nextLetter)
      }
      const preLetter = s[j - 1]
      pMap.set(preLetter, (pMap.get(preLetter) || 0) - 1)
      if(pMap.get(preLetter) === 0){
        pMap.delete(preLetter)
      }
    }
    if(pMap.size === 0){
      res.push(j)
    }
  }
  
  return res
}

var findAnagrams = function(s, p) {
  const sLen = s.length
  const pLen = p.length
  const res = []
  const pStrArr = new Array(26).fill(0)
  const AUnicodePos = 'a'.charCodeAt()
  for (let i = 0; i < p.length; i++) {
    pStrArr[p[i].charCodeAt() - AUnicodePos]++
  }
  if(sLen < pLen || sLen === 0 || pLen === 0) return res
  const sStrArr = new Array(26).fill(0)
  let left = 0
  for (let i = 0; i < sLen; i++) {
    const ele = s[i].charCodeAt() - AUnicodePos
    sStrArr[ele]++
    while(sStrArr[ele] > pStrArr[ele]){
      const leftELe = s[left].charCodeAt() - AUnicodePos
      sStrArr[leftELe]--
      left++
    }
    if(i - left === pLen - 1){
      res.push(left)
    }
    if(left > sLen - pLen){
      break
    }
  }
  return res
}

console.log(findAnagrams('cbaebabacd', 'abc'))
console.log(findAnagrams('abab', 'ab'))
console.log(findAnagrams('abab', 'abc'))

438. 找到字符串中所有字母异位词 #

438. 找到字符串中所有字母异位词