IF - 모든 아나그램 찾기

Goody·2021년 4월 15일
0

알고리즘

목록 보기
90/122

문제

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


예시

Input1Input2Output
bacaAacbaabc3

풀이 및 회고

  • 앞서 풀었던 슬라이딩 윈도우와 해시맵의 혼합 문제이다.
  • 주어진 s문자열에서 모든 원소마다 t 문자열열 갯수만큼 원소를 갖는 서브 배열을 만든다.
  • 서브 배열로 map을 만들고, 문자열을 키로, 문자열의 개수를 값으로 갖게끔 한다.
  • 방금 만든 map을 주어진 t 문자열과 비교해서 일치할때만 count 개수를 1 늘린다.

코드

const solution = (s, t) => {
  let count = 0;

  for (let i = 0; i < s.length; i++) {
    let target = s[i];
    let flag = true;
    for (let j = i + 1; j < i + t.length; j++) {
      target += s[j];
      if (target.length === t.length) {
        let targetMap = new Map();
        for (let str of target) {
          if (targetMap.has(str)) targetMap.set(str, targetMap.get(str) + 1);
          else targetMap.set(str, 1);
        }

        for (let char of t) {
          if (!targetMap.get(char) || targetMap.get(char) === 0) {
            flag = false;
            break;
          } else targetMap.set(char, targetMap.get(char) - 1);
        }

        if (flag) count++;
      }
    }
  }
  return count;
};

0개의 댓글