LeetCode Minimum Window Substring

LeetCode解題之Minimum Window Substring

原題

給定兩個字符串S和T，要求在O(n)的時間內找到包含T中所有字符的S的最短子字符串。

注意點：

例子：

輸入: s = “ADOBECODEBANC”, t = “ABC”

輸出: “BANC”

解題思路

通過前後指針來確定當前的子字符串，先不斷移動後指針，直到子字符串中已經包含了所有T中的字符，嘗試把前指針後移，並不斷刷新最短長度和對應的起始位置，如果移動前指針後不再包含所有T中的字符，則繼續移動後指針。交替移動前後指針，直到遍歷完整個字符串S。

AC源碼

from collections import defaultdict


class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        MAX_INT = 2147483647
        start = end = 0
        char_need = defaultdict(int)    # the count of char needed by current window, negative means current window has it but not needs it
        count_need = len(t)             # count of chars not in current window but in t
        min_length = MAX_INT
        min_start = 0
        for i in t:
            # current window needs all char in t
            char_need[i] += 1           
        while end < len(s):
            if char_need[s[end]] > 0:
                count_need -= 1
            # current window contains s[end] now, so does not need it any more
            char_need[s[end]] -= 1      
            end += 1
            while count_need == 0:
                if min_length > end - start:
                    min_length = end - start
                    min_start = start
                # current window does not contain s[start] any more
                char_need[s[start]] += 1    
                # when some count in char_need is positive, it means there is char in t but not current window
                if char_need[s[start]] > 0: 
                    count_need += 1
                start += 1
        return "" if min_length == MAX_INT else s[min_start:min_start + min_length]


if __name__ == "__main__":
    assert Solution().minWindow("ADOBECODEBANC", "ABC") == "BANC"