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

문제

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

풀이

function solution(s, t) {
  let answer = "";
  let str = "";
  s = s.split("");
  t = t.split("");
  let map2 = new Map();
  for (let x of t) {
    if (map2.has(x)) map2.set(x, map2.get(x) + 1);
    else map2.set(x, 1);
  }
  //console.log(map2);
  for (let i = 0; i < s.length - t.length + 1; i++) {
    str = "";
    let map1 = new Map();
    let cnt = 0;
    for (let k = 0; k < t.length; k++) {
      str += s[i + k];
    }
    for (let x of str) {
      if (map1.has(x)) map1.set(x, map1.get(x) + 1);
      else map1.set(x, 1);
    }
    for (let x of t) {
      map1.set(x, map1.get(x) - 1);
    }
    for (let [key, val] of map1) {
      if (val === 0) {
        cnt++;
      }
    }
    if (cnt === t.length) answer++;
    //console.log(map1);
    //console.log(str);
    // console.log(map1);
  }
  return answer;
}

let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));

 

이중 for 문으로 풀어서 O(n*n)의 형태입니다.

전체 문자열의 for문 한개와 반복되는 문자열의 개수만큼의 for문을 통해 

i가 증가해가면서 예를들어 개수 3개인 문자열 abc 라면 for문의 i 마다 abc의 개수만큼 다른 for문이 도는 형식입니다.

3개의 문자열이 나오면 Map1 에 저장합니다.

 

그리고 for(let x of t)를 통해 3개의 문자열에서 Map1이 t의 문자열들을 가지고 있는지 확인하는 작업입니다.

다른 풀이

function compareMaps(map1, map2) {
  if (map1.size !== map2.size) return false;
  for (let x of [...map2.keys()]) {
    //console.log(x);
    //console.log(map1.has(x));
    if (!map1.has(x) || map1.get(x) === 0) return false;
    map1.set(x, map1.get(x) - 1);
    //console.log(map1);
  }
  return true;
}

function solution(s, t) {
  let answer = 0;
  let str = "";
  t = t.split("");
  s = s.split("");
  let map1 = new Map();
  const map2 = new Map();
  for (let x of t) {
    if (map2.has(x)) map2.set(x, map2.get(x) + 1);
    else map2.set(x, 1);
  }
  //console.log(map2.size);
  for (let i = 0; i < t.length - 1; i++) {
    str += s[i];
  }
  for (let i = t.length - 1; i < s.length; i++) {
    //console.log(str);
    map1 = new Map();
    str = str + s[i];
    //console.log(t.length);
    if (str.length > 3) {
      str = str.split("");
      str.splice(0, 1);
      str = str.join("");
    }
    for (let x of str) {
      if (map1.has(x)) map1.set(x, map1.get(x) + 1);
      else map1.set(x, 1);
    }
    //console.log([...map1.keys()]);
    //console.log(map1.keys());
    //console.log(map1);
    if (compareMaps(map1, map2)) {
      answer++;
    }
    //console.log(compareMaps(map1, map2));
    //console.log(str);
  }
  return answer;
}

let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));

map1 과 map2 를 비교하는 함수를 만들어서 서로 같다면 answer++ 을 해주었습니다

그리고 str.length > 3 이라면 str을 배열로 만들었다가 splice(0,1)로 맨 앞자리를 없애준 후 다시 join 으로문자열을 만들어서 map1을 저장한 후 비교하였습니다.

다른 풀이

function compareMaps(map1, map2) {
  if (map1.size !== map2.size) return false;
  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 str = "";
  //console.log(t.length);
  let map1 = new Map();
  const map2 = new Map();
  for (let x of t) {
    if (map2.has(x)) map2.set(x, map2.get(x) + 1);
    else map2.set(x, 1);
  }
  //console.log(map2.size);
  let len = t.length - 1;
  for (let i = 0; i < len; i++) {
    if (map1.has(s[i])) map1.set(s[i], map1.get(s[i]) + 1);
    else map1.set(s[i], 1);
  }
  //console.log(map1);

  let lt = 0;

  for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) map1.set(s[rt], map1.get(s[rt]) + 1);
    else map1.set(s[rt], 1);
    if (compareMaps(map1, map2)) answer++;
    map1.set(s[lt], map1.get(s[lt]) - 1);
    if (map1.get(s[lt]) === 0) map1.delete(s[lt]);
    lt++;
  }
  return answer;
}

let a = "bacaAacbaabcacbaacba";
let b = "abc";
console.log(solution(a, b));

map1 과 map2 를 비교하는 방식이며 바로 위의 방식과 비슷하지만 이것이 더 보기좋고 간략화 된 코드입니다.

위에서 사용하지 않은 투포인터 방식을 추가로 사용했습니다.