[LeetCode C++] 567. Permutation in String

⭐️ 난이도

 

Medium

---

⭐️ 문제

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

Permutation in String - LeetCode

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

두 개의 string s1과 s2가 주어졌을 때, s2가 s1의 순열을 포함하고 있으면 true를, 그렇지 않으면 false를 반환하라.

 

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

즉, s1의 순열이 s2의 substring이면 true를 반환하라.

 

---

⭐️ Follow-up

 

X

---

⭐️ Idea flow

 

s2에 s1의 순열이 들어가있는 것을 어떻게 알까?

s1의 가능한 수열은 곧 "s1에 있는 문자들을 순서에 상관없이 단 한 번씩 사용"해야 한다.

또한 s1에 있는 알파벳이 각 한 번씩 나온다는 보장이 없다.

 

따라서 s1에서 사용된 각 알파벳의 사용 횟수를 저장하고, 각 알파벳의 사용 횟수가 모두 0이 된다면 s1의 순열이 만들어졌다고 볼 수 있다.

 

[전체적인 알고리즘]

1. s1을 쭉 돌면서 s1에서 사용된 각 알파벳의 사용 횟수 

2. s2의 첫 글자부터 시작해서 s1에서 쓰인적 있는 알파벳인지 확인

2-1. 만일 쓰인 적이 없다면 continue

2-2. 만일 쓰인 적이 있다면 isPermutation 함수를 통해 이후에 이어지는 알파벳이 s1의 순열인지 확인.

 

[bool isPermutation]

시작 위치를 전달 받아 해당 위치부터 시작하여 s2에 s1에서 사용된 알파벳이 순서대로 사용되었는지 확인한다.

 

 

---

⭐️ Code

class Solution {
public:
    bool isPermutation(const string& s1, const string& s2, vector<int> used, int start_idx){
        int cnt = 0, s1_len = s1.length();
        
        for(int i = start_idx; i < s2.length(); i++){
            if(cnt == s1_len)   return true;
            if(used[s2[i]-'a'] > 0){
                used[s2[i]-'a']--;
                cnt++;
            }
            else{
                return false;
            }
        }
        if(cnt == s1_len)   return true;
        return false;
    }
    
    bool checkInclusion(string s1, string s2) {
        vector<int> used(26, 0); // 알파벳은 26글자
        for(int i = 0; i < s1.length(); i++){
            used[s1[i]-'a']++;
        }
        
        for(int i = 0; i < s2.length(); i++){
            if(used[s2[i]-'a'] > 0){ // s1에 있는 글자를 발견했다면
                if(isPermutation(s1, s2, used, i)){
                    return true;
                }
            }
        }
        return false;
    }
};

 

하지만 이와 같은 방법으로 알고리즘을 짜니 검사가 필요없는 구간인데도 검사를 하게 되어 시간이 너무 오래 걸렸다.

 

---

⭐️ Feedback

 

[Sliding window 사용]

 

Discuss를 보니 이 문제를 Sliding window 알고리즘으로 풀 수 있었다.

Sliding window는 창문을 슬라이드하는 것처럼 일정한 구간을 유지해서 붙여진 이름이다.

 

이 Sliding window를 어떻게 적용하느냐?

처음 s1의 알파벳 사용 횟수를 더하는 동시에 s2 또한 진행하면서 각 알파벳이 사용된 횟수도 같이 더해준다.

 

그 다음 반복문을 [len1, len2) 범위로 한 칸 씩 앞으로 간다. 동시에 window의 크기를 len1으로 유지해야 한다.

그러므로 window에서 빠져 나오는 곳(s2[i-len1])의 사용 횟수는 1 줄이고,

window에 새로 들어가는 곳(s2[i])의 사용 횟수는 1 증가시킨다.

 

그러던 중 freq1과 freq2가 같다면, 즉 사용된 알파벳의 종류와 개수가 같다면 s1의 수열이 s2의 substring이라고 볼 수 있을 것 이다.

 

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int len1 = s1.size(), len2 = s2.size();
        if(len1 > len2)
            return false;
           
        vector<int> freq1(26, 0), freq2(26, 0);

        for(int i = 0; i < len1; i++){
            freq1[s1[i]-'a']++; // s1에 있는 알파벳이 쓰인 횟수
            freq2[s2[i]-'a']++; // sliding window - len1만큼 이동하면서 사용된 알파벳 체크
        }
        
        // 두 vector가 같다는 뜻은 각 알파벳이 사용된 횟수가 같다는 뜻
        if(freq1 == freq2)  return true;
        
        for(int i = len1; i < len2; i++){
            freq2[s2[i]-'a']++; // sliding window에 들어갔으므로 사용 횟수 추가
            freq2[s2[i-len1]-'a']--; // sliding window에서 빠져나왔으므로 사용 횟수 -1
            if(freq1 == freq2)  return true;
        }
        
        return false;
    }
};