[알고리즘-JS] 해시(hash) + 아나그램(Anagram) + 투 포인터(two pointer) + 슬라이딩 윈도(Sliding Window)

문제

두 문자열에서 아나그램이 되는 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 대소문자는 구분됩니다.

 

입력 예제

cabbAcabc

abc

 

출력 예제

3

 

 

풀이

// 두 해시 비교
function compareMaps(map1, map2){
  // size가 다르다면 서로 다른 게 담겼다는 의미
  if(map1.size!==map2.size) return false;
  // size는 같은데
  // map2에 해당 키가 없거나
  // map2에서 해당 키를 가져왔는데 값이 다른 경우
  for(let [key, val] of map1){
    if(!map2.has(key) || map2.get(key)!==val) return false;
  }
  return true;
}
function solution(s, t){
  let answer=0;
  let tH = new Map();
  let sH = new Map();
  for(let x of t){
    if(tH.has(x)) tH.set(x, tH.get(x)+1);
    else tH.set(x, 1);
  }
  let len=t.length-1;
  for(let i=0; i<len; i++){
    if(sH.has(s[i])) sH.set(s[i], sH.get(s[i])+1);
    else sH.set(s[i], 1);
  }
  
  let lt=0;
  for(let rt=len; rt<s.length; rt++){
    // 해시 세팅
    if(sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt])+1);
    else sH.set(s[rt], 1);
    // 3개부터 두 해시 비교
    if(compareMaps(sH, tH)) answer++;
    // 슬라이드 윈도 하나씩 나아가면서 맨 앞에 있는 요소 개수 -1
    sH.set(s[lt], sH.get(s[lt])-1);
    // 0이면 아예 지우기
    if(sH.get(s[lt])===0) sH.delete(s[lt]);
    lt++;
  }
  return answer;
}