Portfolio

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:


Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:


Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

1 <= s1.length, s2.length <= 104

s1 and s2 consist of lowercase English letters.

풀이

은찬


/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
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;
};

재영


/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
 const checkInclusion = (s1, s2) => {
    let start = 0; 
    let end = 0;

    const counts = {};
    for (let i = 0; i < s1.length; i += 1) {
        const now = s1[i];
        counts[now] = (counts[now] ?? 0) + 1
    }

    for (let i = 0; i < s1.length; i += 1) {
        if (counts[s2[i]] !== undefined) {
            counts[s2[i]] -= 1;
        }
    }

    end = s1.length - 1;

    while (end < s2.length) {
        if (Object.values(counts).every(v => v === 0)) return true;

        if (counts[s2[start]] !== undefined) {
            counts[s2[start]] += 1; // initialized
        }

        if (end + 1 < s2.length && counts[s2[end + 1]] !== undefined) {
            counts[s2[end + 1]] -= 1; // initialized
        }

        start += 1;
        end += 1;
    }


    return false;
};

Permutation in String

풀이