[leetcode] Minimum Window Substring

유의할점

최적화 가능함. 생각해볼것.

풀이

s가 t를 포함해야한다. t의 char값을 key로 하고 개수를 값으로 하는 map을 만든다.

그리고 map을 reqAlphabet이라고 하자.

투포인터를 사용할것이다. startPointer와 endPointer 두개의 포인터를 사용할것이며, endPointer의 값은 포함하지 않는 값이다. 투포인터로 만들어내는 영역을 window라고 하자.

map의 값들은 이렇게 해석하자. key(character)의 value값은 해당 character가 우리가 만들어낸 window에 필요한 개수로 정의한다.

그렇게 되면 map의 모든 값들이 0이하가 되어야 현재 window에서 찾았다고 할수있다.

map의 모든 값들을 검사하며 0을 초과하는 값이 나올경우 flag값을 false로 하여 현재 window값이 확장이 필요함을 알린다.

flag값이 true인 경우는 0을 초과하는 값이 나오지 않을 경우이다. 해당 window는 값을 모두 포함한다. 따라서 startPointer을 증가시킨다. 이때 증가시키면서 startPointer값이 map에 존재할경우 해당값을 증가시킨다. 이후 window는 줄어든다.

flag값이 false인 경우는 확장이 필요한 경우이다. 이때 endPointer가 n인경우는 더 이상 확장이 안되는 경우이다. 따라서 해당 경우 endPointer를 증가시킬수없기때문에 값을 그대로 반환한다.

endPointer가 n이 아닌 경우 해당값을 window에 추가하고 값을 증가시키므로써 window를 확장한다.

코드

C++

class Solution {
public:
    string minWindow(string s, string t) {
        map <char,int> reqAlphabet;
        for(char c : t)
            reqAlphabet[c]++;
        int startPointer = 0;
        int endPointer = 0;
        int n = s.size();
        string resS = ""; 
        while(startPointer!=n){
            //현재 찾았는가
            bool flag = true;
            for(auto it:reqAlphabet)
                if(it.second>0){
                    flag = false;
                    break;
                }
            //t가 s에 포함되는 경우
            if(flag){
                int findSize = endPointer - startPointer;
                if(resS.size()==0||resS.size()>findSize)
                    resS = string(s.begin()+startPointer,s.begin()+endPointer);
                if(reqAlphabet.find(s[startPointer])!=reqAlphabet.end())
                    reqAlphabet[s[startPointer]]++;
                startPointer++;
            }
            //t가 s에 포함되지 않는 경우
            else{
                //더 이상 확장이 안되는 경우
                if(endPointer==n)
                    return resS;
                if(reqAlphabet.find(s[endPointer])!=reqAlphabet.end())
                    reqAlphabet[s[endPointer]]--;
                endPointer++;
            }
            
        }
        return resS;
    }
};