Minimum Window Substring

题目描述

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".

解题方法

找最短，最长，各种substring的基本方法！two pointer!

用hashtable来快速判断一个character是否在t里面，再加一个variable来判断是否t 的所有character都被包含了。

Solution

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if not t or not s:
            return ""
        t_map = {}
        num_t = 0
        for c in t:
            if c in t_map:
                t_map[c] += 1
            else:
                t_map[c] = 1
                num_t += 1

        length_s = len(s)
        min_start = 0
        min_end = 0
        min_length = sys.maxint
        p_1 = 0
        p_2 = 0
        while p_1 < length_s:
            while p_2 < length_s and num_t > 0: #条件未满足时，不断移动pointer 2
                if s[p_2] in t_map:
                    t_map[s[p_2]] -= 1 # can be negative
                    if t_map[s[p_2]] == 0:
                        num_t -= 1
                p_2 += 1
            if num_t == 0 and min_length > p_2 - p_1: # 更新条件
                min_start = p_1
                min_end = p_2
                min_length = p_2 - p_1
            if s[p_1] in t_map:
                t_map[s[p_1]] += 1
                if t_map[s[p_1]] == 1: # char comes back
                    num_t += 1
            p_1 += 1  # 移动pointer 1
        return s[min_start: min_end]

Reference