567.字符串的排列

链接：567.字符串的排列
难度：Medium
标签：哈希表、双指针、字符串、滑动窗口
简介：给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

题解 1 - typescript

• 编辑时间：2021-02-10
• 执行用时：340ms
• 内存消耗：46.3MB
• 编程语言：typescript
• 解法介绍：利用 map 储存遍历过的值。

function checkInclusion(s1: string, s2: string): boolean {
  const len1 = s1.length;
  const getMap = (arr: string[]) =>
    arr.reduce((total, cur) => {
      total[cur] = (total[cur] ?? 0) + 1;
      return total;
    }, {} as Record<string, number>);
  const charMap1 = getMap(s1.split(''));
  const charMap2 = getMap(s2.substr(0, len1).split(''));
  const check = () => Object.entries(charMap1).every(([k, v]) => charMap2[k] === v);
  if (check()) return true;
  for (let i = len1, len2 = s2.length; i < len2; i++) {
    charMap2[s2[i - len1]]--;
    charMap2[s2[i]] = (charMap2[s2[i]] ?? 0) + 1;
    if (check()) return true;
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2021-02-10
• 执行用时：304ms
• 内存消耗：46.3MB
• 编程语言：typescript
• 解法介绍：增加 set 优化题解 1。

function checkInclusion(s1: string, s2: string): boolean {
  const len1 = s1.length;
  const getMap = (arr: string[]) =>
    arr.reduce((total, cur) => {
      total[cur] = (total[cur] ?? 0) + 1;
      return total;
    }, {} as Record<string, number>);
  const arr1 = s1.split('');
  const map1 = getMap(arr1);
  const set1 = new Set(arr1);
  const map2 = getMap(s2.substr(0, len1).split(''));
  const check = () => Object.entries(map1).every(([k, v]) => map2[k] === v);
  if (check()) return true;
  for (let i = len1, len2 = s2.length; i < len2; i++) {
    const char = s2[i];
    map2[s2[i - len1]]--;
    map2[char] = (map2[char] ?? 0) + 1;
    if (!set1.has(char)) continue;
    if (check()) return true;
  }
  return false;
}