[알고리즘] LeetCode 438. Find All Anagrams in a String JS

개요

s, p 두 가지 문자열이 주어지는데 이때 p가 순서 상관없이 s의 부분집합이 되는 모든 인덱스를 찾는 문제였다

Find All Anagrams in a String - LeetCode

 

풀이

s 문자열을 계속 해쉬로 파싱하면서 p 문자열과 비교하여 풀었다.

JS의 단점으로 map자료구조가 서로 같은지 비교하는게 안되어 직접 코드를 작성해줘야한다는 점이 조금 불편했다.

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 *
 * p의 길이 만큼 문자열 s를 잘랐을 때 순서 상관없이 p 문자열이 될 수 있다면 해당 인덱스를 반환한다
 *
 * 해쉬 + 슬라이딩 윈도우
 */
const compareHash = (map, checkmap) => {
  for (const key of map.keys()) {
    if (!checkmap.has(key) || map.get(key) !== checkmap.get(key)) return false;
  }
  return true;
};

var findAnagrams = function (s, p) {
  const answer = [];
  const len = p.length;
  const slen = s.length;
  const map = new Map();
  const checkmap = new Map(); // 계속 움직이는 해쉬맵
  let lt = 0;
  let rt = len - 1;

  if (len > slen) return [];

  // p로 hashmap 만들기
  for (const char of p) {
    if (map.has(char)) map.set(char, map.get(char) + 1);
    else map.set(char, 1);
  }

  for (let i = 0; i < len; i++) {
    if (checkmap.has(s[i])) checkmap.set(s[i], checkmap.get(s[i]) + 1);
    else checkmap.set(s[i], 1);
  }

  while (rt < slen) {
    if (compareHash(map, checkmap)) answer.push(lt);
    if (checkmap.get(s[lt]) === 1) checkmap.delete(s[lt]);
    else checkmap.set(s[lt], checkmap.get(s[lt]) - 1);
    lt += 1;
    rt += 1;
    if (checkmap.has(s[rt])) checkmap.set(s[rt], checkmap.get(s[rt]) + 1);
    else checkmap.set(s[rt], 1);
  }
  return answer;
};