2023-02-04.md

题目

567. Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

思路

代码

// runtime 94.19% memory 90.78%
var checkInclusion = function(s1, s2) {
  const len_s1 = s1.length
  const len_s2 = s2.length
  const freq_s1 = Array(26).fill(0)
  const freq_window = Array(26).fill(0)

  if (len_s2 < len_s1) {
    return false
  }
  for (let i = 0; i < len_s1; i++) {
    freq_s1[s1.charCodeAt(i)-97]++
    freq_window[s2.charCodeAt(i)-97]++
  }
  if (isEqual(freq_s1, freq_window)) {
    return true
  }
  for (let i = len_s1; i < len_s2; i++) {
    freq_window[s2.charCodeAt(i-len_s1)-97]--
    freq_window[s2.charCodeAt(i)-97]++
    if (isEqual(freq_s1, freq_window)) {
      return true
    }
  }
  return false
}
function isEqual(array1, array2) {
  return array1.length === array2.length && array1.every((value, index) => value === array2[index])
}