LeetCode 567. Permutation in String

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

Permutation in String - LeetCode

 

문제 요약

 

문자열 s2에 s1의 '조합'이 존재하는지 판단하세요. 

예를 들어 다음과 다음과 같은 경우엔 s2에 s1이 존재합니다.

 

핵심 포인트

 

조합이라는 단어를 들으면 next_permutation 함수가 떠오르지만, 이 문제는 s1의 길이가 최대 10^4까지 이므로, next_permutation을 사용했다가는 시간초과가 발생합니다. 대신 윈도우 슬라이싱 기법을 쓰면 쉽게 풀 수 있습니다.

 

 

문제 풀이

 

1. 필요한 변수들을 선언하고 값을 저장합니다.

        int sone[26], stwo[26]; // 1
        memset(sone,0,sizeof(sone)); // 2
        memset(stwo,0,sizeof(stwo));
        for(int i=0; i<s1.size(); i++) sone[s1[i]-'a']++; // 3

(1) sone은 s1에 저장된 알파벳 갯수를 세어줄 배열이며, stwo는 s2에 저장된 알파벳 갯수를 세어줍니다.

(2) 각 배열들을 모두 0으로 초기화합니다.

(3) s1에 저장된 알파벳들을 sone배열에 저장합니다.

 

2. s2의 사이즈만큼 for문을 진행합니다.

        for(int i=0; i<s2.size(); i++){
            stwo[s2[i]-'a']++; // 1
            if(i>=s1.size()) stwo[s2[i-s1.size()]-'a']--; // 2
            if(i>=s1.size()-1&&checkPermutation(sone,stwo)) return true; // 3
        }

(1) 현재 s2의 위치에 해당되는 알파벳을 stwo배열에 저장합니다.

(2) 이 부분은 슬라이싱 윈도우 기법의 핵심입니다. 현재 위치가 s1의 사이즈 이상일 경우, stwo[i-s1.size()]에 해당되는 알파벳 배열의 값을 -1합니다. 이렇게 해서 온전히 s1 사이즈 만큼의 값들 만큼 sone과 stwo배열에 저장하여 값의 차이를 비교할 수 있습니다.

(3) 만약 현재 i가 s1의 사이즈 이상이고, checkPermutation의 함수로 반환된 결과가 true일 경우 true를 반환합니다.

 

    bool checkPermutation(int s1[], int s2[]){
        for(int i=0; i<26; i++){
            if(s1[i]!=s2[i]) return false;
        }
        return true;
    }

위의 코드가 checkPermutation 함수입니다. sone과 stwo에 저장된 배열의 차이를 비교합니다. 만약 하나라도 값의 크기가 다를 경우 false를 반환합니다.

 

3. for문을 빠져나올 경우 s1의 조합을 s2에서 찾지 못했다는 뜻이므로, false를 반환합니다.

 

class Solution {
public:
    bool checkPermutation(int s1[], int s2[]){
        for(int i=0; i<26; i++){
            if(s1[i]!=s2[i]) return false;
        }
        return true;
    }
  
    bool checkInclusion(string s1, string s2) {
        int sone[26], stwo[26];
        memset(sone,0,sizeof(sone));
        memset(stwo,0,sizeof(stwo));
        for(int i=0; i<s1.size(); i++) sone[s1[i]-'a']++;
        for(int i=0; i<s2.size(); i++){
            stwo[s2[i]-'a']++;
            if(i>=s1.size()) stwo[s2[i-s1.size()]-'a']--;
            if(i>=s1.size()-1&&checkPermutation(sone,stwo)) return true;
        }
        return false;
    }
};