[Leetcode] 76. Minimum Window Substring

Identifying the Problem

문자열 s, t에서 t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구한다.

만약 정답이 없다면 빈 문자열 리턴한다.

Organizing thoughts

 

아이디어 출처

Sourcecode

이 코드는 내가 작성한 코드인데, O(n²)가 되어 매우 긴 경우 오류가 난다.

class Solution {
public:
    string minWindow(string s, string t) 
    {
        int t_lettermap[128] = {0};
        int w_lettermap[128] = {0};
        
        int s_len = s.length();
        int t_len = t.length();
        int left = 0;
        int right = 0;
        
        int min = s_len;
        string ans = "";
        
        if(s.compare(t) == 0) return s;
        else if(t_len > s_len) return "";
        else if(t_len == 1 && s_len == 1 && s[0] != t[0]) return "";
        
        for(int i =0; i<t_len; i++)
            t_lettermap[t[i]] +=1;
        
        while(left <= s_len - t_len)
        {
            w_lettermap[s[right]] += 1;
            
            if(left == 0 && right == s_len && !flag(w_lettermap, t_lettermap, t))
            { return "";}
            
            if(flag(w_lettermap, t_lettermap, t))
            {
                
                if(right - left + 1 <= min)
                {
                    min = right - left + 1;
                    ans = s.substr(left,right-left+1);
                }
                
                left++;
                right = left;
                memset(w_lettermap,0,sizeof(w_lettermap));
            }
            
            else right++;
          
            
            if(right == s_len)
            {
                left++;
                right = left;
                memset(w_lettermap,0,sizeof(w_lettermap));
            }
            
            
        }
    
        
        return ans;
    }
    bool flag(int* w_map, int* t_map, string t)
    {
        for(int i=0; i<t.length();i++)
        {
            if(w_map[t[i]] < t_map[t[i]])
            { return false;}
        }
        
        return true;
    }
};

가장 심플한 버전의 코드 (출처 : solution - v1s1on )

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> hist(128, 0);
        for (char c : t) hist[c]++;
        
        int remaining = t.length();
        int left = 0, right = 0, minStart = 0, minLen = numeric_limits<int>::max(); 
        									//int의 최대값
        while (right < s.length()){
            if (--hist[s[right++]] >= 0) remaining--;
            while (remaining == 0){
                if (right - left < minLen){
                    minLen = right - left;
                    minStart = left;
                }
                if (++hist[s[left++]] > 0) remaining++;
            }
        }
            
        return minLen < numeric_limits<int>::max() ? s.substr(minStart, minLen) : "";
    }
            

};

 

New things learned

하나의 반복이 끝났을 때, 초기화할 변수는 없는지 다시 한번 생각해보자