모든 아나그램 찾기 (해쉬, 투포인터, 슬라이딩 윈도우 적용) - Node.js

모든 아나그램 찾기 (해쉬, 투 포인터, 슬라이딩 윈도우)

---

문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

입력

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

출력

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

입력 예시 1

bacaAacba

abc

출력 예시 1

3

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

---

해결방법

function compareMaps(map1, map2) {
  if (map1.size !== map2.size) {
    return false;
  }
  for (let [key, value] of map1) {
    if (!map2.has(key)) {
      return false;
    }
    if (map2.get(key) !== value) {
      return false;
    }
  }
  return true;
}
function solution(s, t) {
  let answer = 0;
  let tHASH = new Map();
  let sHASH = new Map();

  for (let x of t) {
    if (tHASH.has(x)) {
      tHASH.set(x, tHASH.get(x) + 1);
    } else {
      tHASH.set(x, 1);
    }
  }
  let length = t.length - 1;
  for (let i = 0; i < length; i++) {
    if (sHASH.has(s[i])) {
      sHASH.set(s[i], sHASH.get(s[i]) + 1);
    } else {
      sHASH.set(s[i], 1);
    }
  }

  let lt = 0;
  // rt = 2
  for (let rt = length; rt < s.length; rt++) {
    if (sHASH.has(s[rt])) {
      sHASH.set(s[rt], sHASH.get(s[rt]) + 1);
    } else {
      sHASH.set(s[rt], 1);
    }
    if (compareMaps(sHASH, tHASH)) {
      answer++;
    }

    sHASH.set(s[lt], sHASH.get(s[lt]) - 1);
    if (sHASH.get(s[lt]) === 0) {
      sHASH.delete(s[lt]);
    }
    lt++;
  }

  return answer;
}

// 개선 코드
// function solution(s, t) {
//   let answer = 0;
//   let sH = new Map();
//   for (let x of t) {
//     sH.set(x, (sH.get(x) || 0) - 1);
//   }
//   let len = t.length - 1;
//   for (let i = 0; i < len; i++) {
//     sH.set(s[i], (sH.get(s[i]) || 0) + 1);
//     if (sH.get(s[i]) === 0) sH.delete(s[i]);
//   }
//   let lt = 0;
//   for (let rt = len; rt < s.length; rt++) {
//     sH.set(s[rt], (sH.get(s[rt]) || 0) + 1);
//     if (sH.get(s[rt]) === 0) sH.delete(s[rt]);
//     if (sH.size === 0) answer++;
//     sH.set(s[lt], (sH.get(s[lt]) || 0) - 1);
//     if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
//     lt++;
//   }
//   return answer;
// }
// console.log(solution('bacacbcba', 'abc'));

const a = 'bacaAacba';
const b = 'abc';
console.log(solution(a, b));

---