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

문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드)

 

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

 

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

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

 

▣ 입력예제 1

bacaAacba

abc

 

▣ 출력예제 1

3

 

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

 

Tip

 

문제풀이

//강의 설명만 듣고 내가 작성한 답
function compare(h1,h2){
    if(h1.size !== h2.size) return false;
    for(let [key,val] of h1){
        // if(h1.get(key) !== h2.get(key)) return false;
        if(!h2.has(key)) return false;
        if(h2.get(key) !== val) return false;
    }
    return true;
}

function solution(str1, str2){
    let answer = 0;
    let sH = new Map();
    let tH = new Map();

    //tH
    for(let x of str2){
        if(tH.has(x))tH.set(x, tH.get(x)+1);
        else tH.set(x,1);
    }
    //sH
    for(let i = 0 ; i < str2.length-1 ; i++){
        if(sH.has(str1[i])) sH.set(str1[i], sH.get(str1[i])+1);
        else sH.set(str1[i],1);
    }



    //투 포인트와 동시에 슬라이딩 윈도우를 밀고가는것이 둘 다 추상적 개념이다.
    let lt = 0;
    console.log('str1 >>>>', str1)
    for(let rt = str2.length - 1 ; rt < str1.length ; rt++){
        console.log('rt >>>', rt)
        if(sH.has(str1[rt])) {
            console.log('condition 1 >>>> ', true);
            sH.set(str1[rt], sH.get(str1[rt])+1);
        }
        else {
            console.log('case else')
            sH.set(str1[rt],1);
        }
        if(compare(sH,tH)) {
            console.log('condition 2 >>>> ', true);
            answer++;
        }

        sH.set(str1[lt],sH.get(str1[lt])-1);
        console.log('sH >>>', sH);

        if(sH.get(str1[lt]) === 0) {
            console.log('condition 3 >>> ', true);
            sH.delete(str1[lt]);
        }
        lt++;
    }
    return answer;
}

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