[SlidingWindow][Medium] 567. Permutation in String

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

 

두개의 문장 s1과 s2가 주어질 때, s1의 permutation이 s2에 포함되어 있는지 여부를 반환하라. 

 

문제자체는 간단하다. 

다면 겹치는 경우에 대한 고려를 해야 한다. 

 

따라서 유효하지 않는 경우, 즉 s1의 문자가 s2에 존재하지 않게 되면

존재하도록 left를 당기도록 만들고 

s1의 문자를 제거한다. 

 

모두 제거되면 s1에 대한 permutation이 있다고 판단할 수 있다.

 

코드 

bool checkInclusion(string s1, string s2) 
{
    map<char, int> mapFreq;
    for (int k = 0; k < s1.size(); ++k)
        mapFreq[s1[k]]++;

    int left = 0, right = 0;
    for (; right < s2.size(); ++right)
    {
        char cur = s2[right];

        while (mapFreq.find(cur) == mapFreq.end())
        {
            char leftCur = s2[left];
            mapFreq[leftCur]++;
            left++;
        }
        mapFreq[cur]--;
        if (mapFreq[cur] == 0)
            mapFreq.erase(cur);

        if (mapFreq.size() == 0)
            return true;
    }
    return false;
}

 

 

결과