문자열 안의 문자열 찾는 문제 관련 템플릿

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems 정리.

위 문서는 아래에 적을 슬라이딩 윈도우 알고리즘 템플릿으로 여러가지 문자열 안의 문자열 문제들을 풀 수 있다는걸 알려줌.

파이썬으로 설명. https://leetcode.com/problems/minimum-window-substring/ 문제의 해답임.

기본적으로 two pointer 알고리즘에서 만든 템플릿이다. 

문제는 S와 T가 있는데 S안에 T단어 전체가 들어가는 가장 작은 윈도우의 길이를 리턴하는 문제이다.

class Solution(object):
    def minWindow(self, s, t):
        if len(t) > len(s):
            return ''
        
        result = []
        _dict = {}
        for tt in t:
            _dict[tt] = _dict.get(tt, 0) + 1  # _dict에 t의 갯수들을 넣어놓는다. _dict의 키는 문자, 값은 문자의 빈도수를 나타낸다.
            
        counter = len(_dict)  # counter변수는 _dict의 길이를 저장하기 위해 쓴다.
        begin = end = head = 0
        _len = 999999999
        while end < len(s):  # two pointer인데 end가 한칸씩 뒤로 가면서 begin이 나중에 따라오는 포맷이다.
            print 'b,e =',begin,end,counter  # 로그용
            c = s[end]  # end인덱스의 문자를 가져와서 이게 존재해야 하는 T의 문자열을 저장해놓은 dict에 있는지 보고 counter를 _dict의 길이에 맞게 조정해준다.
            if c in _dict:
                _dict[c] -= 1
                # 여기서 end가 증가할수록 _dict 에서 1개씩 빼는 이유는 T의 모든 문자가 들어가는 범위를 덮기 위해서이다. 그래서 계속 end를 증가시키면서 
                # 두번째 반복문인 counter == 0를 만족시키기 전까지 반복한다. counter는 _dict 즉 들어가야 하는 T가 저장된 dict의 길이 counter == 0의 의미는 T가 begin과 end사이에 전부 들어갔다는 소리이다.
                if _dict[c] == 0:
                    counter -= 1
            end += 1
            
            while counter == 0:  # T가 begin, end사이에 전부 존재할 경우만 여기로 들어온다. 전부 존재하지 않을 경우 end만 증가시킨다.
                print 'in'
                tempc = s[begin]
                if tempc in _dict:
                    _dict[tempc] += 1  # 위에서 end를 증가시키면서 _dict에서 카운트를 줄여줬는데, begin을 증가시키면서는 카운트를 증가시켜준다. 그래야 위쪽에서 찾았을때 다시 뺄수 있으니까.
                    if _dict[tempc] > 0:
                        counter += 1

                # 이 아래는 문제의 조건에 따라 달라질 수 있다. 
                if end - begin < _len:
                    _len = end - begin
                    head = begin
                begin += 1
            print s[head:head+_len]
        if _len == 999999999:
            return ''
        return s[head: head+_len]

템플릿을 제대로 변형해서 쓰려면 저 링크에 있는 문제를 다 풀어봐야 소스코드도 제대로 이해가 되고 응용력이 높아진다.

https://qkqhxla1.tistory.com/1062?category=685989