[못풀었다/릿코드/javascript]. 567. Permutation in String

순열으로 풀었는데, 메모리에러가 났다.

굳이 순열으로 풀 필요없이 투포인터를 이용해서 풀면 된다.

 

var checkInclusion = function (s1, s2) {
    if(s1.length>s2.length) return false;
    //s1의 길이가 더 크다면 볼것도 없으므로 false 리턴함
    let left = 0;
    let right = 0;
    const neededChar = {}
    let neededLen = s1.length;
    for(let i=0;i<s1.length;i++){
        if(!neededChar[s1[i]]) neededChar[s1[i]]=0
        neededChar[s1[i]]++;
    }
    //s1에 있는 알파벳들의 갯수를 neededChar에 저장해 주었다.
    while(right<s2.length){
    //right이 s2의 끝까지 갈때까지 돌면 됨.
    //우리는 window = s2.slice(left,right)인 window를 볼것임.
        if(neededChar[s2[right]]>0) neededLen--;
        //만약 s2[right]이 s1에 있다면(needChar에 있다면) needLen--해준다.
        //즉 하나는 찾았으니 필요한 갯수(needLen)이 줄어든거임.
        neededChar[s2[right]]--;
        //neededChar도 빼줘야 a가 하나만 필요한데 두번 세번 계산하는것을 막을 수 있음
        right++;
        //포인터를 앞쪽으로 옮김
        if(neededLen===0) return true;
        //하다가 needLen이 0이되면 즉 window===s1의 순열 중 하나가되면 true리턴해줌,
        if((right-left)>=s1.length){
        //근데 이제 s1이 s2에 연속적으로 위치해야됨. 즉 right-left===s1.length이렇게되면
        //다음턴에서 right-left>s1.length이렇게 되니까 우리가 보려고 하는 window의 크기가 s1보다 커져버림
        //그런일은 일어나선 안되니 left를 한칸 이동해줄것임.
            if(neededChar[s2[left]]>=0) neededLen++;
            //이 left가 needLen에 영향을 주었다면 원상복귀해줌
            neededChar[s2[left]]++;
            //neededChar도 원상복귀해줌
            left++;
            //이제서야 한칸 이동해줄 수 있음.
        }
    }
    return false
}