sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

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

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

438.找到字符串中所有字母异位词 给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。

说明:

字母异位词指字母相同,但排列不同的字符串。 不考虑答案输出的顺序。

示例  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" 的字母异位词。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

还是典型的滑动窗口去解决的问题,由于字母异位词一定是长度相等的,所以我们需要把窗口的长度始终维持在目标字符的长度,也就是说,每次循环结束后 leftright 是同步前进的。

由于字母异位词不需要考虑顺序,所以只需要运用一个辅助函数 isAnagrams 去判断两个 map 中记录的字母次数,即可判断出当前位置开始的子串是否和目标字符串形成字母异位词。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
let findAnagrams = function (s, p) {
  let targetMap = makeCountMap(p)
  let sl = s.length
  let pl = p.length
  // [left,...right] 滑动窗口
  let left = 0
  let right = pl - 1
  let windowMap = makeCountMap(s.substring(left, right + 1))
  let res = []

  while (left <= sl - pl && right < sl) {
    if (isAnagrams(windowMap, targetMap)) {
      res.push(left)
    }
    windowMap[s[left]]--
    right++
    left++
    addCountToMap(windowMap, s[right])
  }

  return res
}

let isAnagrams = function (windowMap, targetMap) {
  let targetKeys = Object.keys(targetMap)
  for (let targetKey of targetKeys) {
    if (
      !windowMap[targetKey] ||
      windowMap[targetKey] !== targetMap[targetKey]
    ) {
      return false
    }
  }
  return true
}

function addCountToMap(map, str) {
  if (!map[str]) {
    map[str] = 1
  } else {
    map[str]++
  }
}

function makeCountMap(strs) {
  let map = {}
  for (let i = 0; i < strs.length; i++) {
    let letter = strs[i]
    addCountToMap(map, letter)
  }
  return map
}