leetcode 문자열 안의 문자열 찾는 문제들 76, 159, 3, 438

https://qkqhxla1.tistory.com/1061 에 이론을 정리해두고 아래는 응용 방법들을 정리해둠.

76. https://leetcode.com/problems/minimum-window-substring/

S와 T가 있고, T의 모든 문자가 S에 포함되는 S의 가장 짧은 부분문자열의 길이를 구하여라.

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
            
        counter = len(_dict)
        begin = end = head = 0
        _len = 999999999
        while end < len(s):
            c = s[end]
            if c in _dict:
                _dict[c] -= 1
                if _dict[c] == 0:
                    counter -= 1
            end += 1
            
            while counter == 0:
                tempc = s[begin]
                if tempc in _dict:
                    _dict[tempc] += 1
                    if _dict[tempc] > 0:
                        counter += 1
                if end - begin < _len:  # 현재 문자열보다 더 짧은 문자열이면 저장
                    _len = end - begin
                    head = begin
                begin += 1
        if _len == 999999999:
            return ''
        return s[head: head+_len]

159. https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

s의 부분문자열중 두 문자만 들어간 부분문자열의 가장 긴 길이를 구하여라.

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        _dict = {}
            
        counter = 0
        begin = end = 0
        _len = 0
        while end < len(s):
            c = s[end]
            _dict[c] = _dict.get(c, 0) + 1  # 여기서는 위와 다르게 end를 증가시키면서 c를 저장해둠.
            if _dict[c] == 1:
                counter += 1  # counter에는 _dict의 길이를, 즉 distinct인 문자열의 길이가 저장됨.
            end += 1
            
            while counter > 2:  # distinct한 문자열이 2개 이상일때는 들어가서 begin을 증가시키면서 2개로 맞추고 나옴.
                tempc = s[begin]
                if tempc in _dict:
                    _dict[tempc] -= 1
                    if _dict[tempc] == 0:
                        counter -= 1
                begin += 1
            _len = max(_len, end-begin)  # 문자열의 최대 길이를 저장해둠.
        return _len

3. https://leetcode.com/problems/longest-substring-without-repeating-characters/

이건 최근에 https://qkqhxla1.tistory.com/1059?category=685989 에서 풀었었는데 다시 이 템플릿으로 풀어봄.

가장 긴 반복하지 않는 문자열의 길이를 구하는 거다.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        _dict = {}
            
        counter = 0
        begin = end = 0
        _len = 0
        while end < len(s):
            c = s[end]
            _dict[c] = _dict.get(c, 0) + 1  # 문자열을 _dict에 저장해둔다.
            if _dict[c] > 1:
                counter += 1  # counter에는 위의 문제들과 다르게 중복되는 문자열이 있으면 그 갯수를 저장해둔다.
            end += 1
            
            while counter > 0:  # 중복되는 문자열이 있는 경우 begin을 증가시키면서 제거해준다.
                tempc = s[begin]
                if tempc in _dict:
                    _dict[tempc] -= 1
                    if _dict[tempc] == 1:  # begin으로 한 문자열이 지워졌는데 지워지고 나서 중복되는 문자열이 더이상 아니게 된 경우.(1개만 존재) counter를 1 줄여준다.
                        counter -= 1
                begin += 1
            _len = max(_len, end-begin)
        return _len

438. https://leetcode.com/problems/find-all-anagrams-in-a-string/

이것도 이전에 https://qkqhxla1.tistory.com/1039에서 풀었었는데 위 템플릿으로 다시 품.

class Solution(object):
    def findAnagrams(self, s, p):
        ret = []
        _dict = {}
        for pp in p:
            _dict[pp] = _dict.get(pp, 0) + 1
        
        counter = len(_dict)
        begin = end = 0
        _len = len(p)
        while end < len(s):
            c = s[end]
            if c in _dict:
                _dict[c] -= 1
                if _dict[c] == 0:
                    counter -= 1
            end += 1
                        
            while counter == 0:  # 모든 문자가 있는 경우에 들어옴.
                tempc = s[begin]
                if tempc in _dict:
                    _dict[tempc] += 1
                    if _dict[tempc] > 0:
                        counter += 1
                        
                if end - begin == _len:  # 모든 문자가 있는데 길이가 찾아야 하는 아나그램의 길이와 같으면 아나그램이라고 볼 수 있음.
                    ret.append(begin)
                begin += 1
        return ret