(Leet Code JS)Permutation in String

https://leetcode.com/problems/permutation-in-string/

Permutation in String - LeetCode

HashMap을 이용.

 

문제는 풀었지만 시간이 간당간당하게 통과해서, 더 큰 문자열이 들어오면 다른 알고리즘을 써야할 것 같다.

투포인터를 이용한 문제인 것 같다.

 

map을 선언해서 s1에 존재하는 모든 문자를 카운팅한다.

이후 s2를 순회하면서, map에 해당 문자가 있는지 확인한다.

 

만약 값이 있다면,

새로운 맵을 선언하고, s1의 map을 복사한다.

j = 0 ~ s1.length만큼 반복하면서 s2의 문자를 하나씩 확인한다.

확인하면서 checkMap에 있는 카운팅을 줄여가며,

만약 카운팅이 0이 된다면 해당 문자를 checkMap에서 지워준다.

문자가 checkMap에 없다면 break.

 

내부 for문을 확인한 후, checkMap이 비어있다면 true를 리턴.

모든 for문이 끝나도 없다면 false를 리턴한다.

const checkInclusion = (s1, s2) => {
    const map = new Map();
    const length = s1.length;
    
    for(let i = 0; i < s1.length; i++){
        const val = map.get(s1[i]) || 0;
        
        map.set(s1[i], val + 1);
    }
    
    for(let i = 0; i < s2.length; i++){
        if(map.has(s2[i])){
            const checkMap = new Map(map);
            
            for(let j = 0; j < s1.length; j++){
                const key = s2[i + j];
                const val = checkMap.get(key);
                
                if(!val){
                    break;
                }
                
                if(val - 1 === 0){
                    checkMap.delete(key);
                } else{
                    checkMap.set(key, val - 1);
                }
            }
            
            if(checkMap.size === 0){
                return true;
            }
        }
    }
    
    return false;
};