【LeetCode】76. Minimum Window Substring 解题报告（Python），leetcodesubstring

【LeetCode】76. Minimum Window Substring 解题报告（Python）

作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

---

题目地址: https://leetcode.com/problems/minimum-window-substring/description/

题目描述：

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string “”.
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

题目大意

在S中找出包含T的全部字符的最小子串。

解题方法

统计字符出现的个数，而且时间复杂度要求O(N)，明显使用双指针解题。和567. Permutation in String有点相似，都是要求子字符串满足一定的次数要求。

使用right指针向右搜索，同时要记录在left～right这个区间内包含的T中每个元素出现的个数和。如果在[left,right]区间内，元素出现的个数和与T长度相等了，说明在这个区间是符合要求的一个区间，但是不一定是最短区间。

因此，现在要移动left指针，要求，在[left, right]区间内的元素出现个数应该把T中所有的元素都包含。同样使用cnt来验证是否包含了T所有的元素。

在移动left指针的时候要注意存储最短的子串，当所有的循环都结束之后最短字符串即为题目要求了。

这个题难点就在于维护cnt，其实如果使用普通的求T的元素个数是不是S[left, right]的元素子集的方法应该更容易理解，但是不知道能不能通过OJ。这个思路比较重要，其他都还好。

时间复杂度是O(N)，空间复杂度是O(N)。

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        res = ""
        left, right, cnt, minLen = 0, 0, 0, float('inf')
        tcount = collections.Counter(t)
        scount = collections.defaultdict(int)
        while right < len(s):
            scount[s[right]] += 1
            if s[right] in tcount and scount[s[right]] <= tcount[s[right]]:
                cnt += 1
            while left <= right and cnt == len(t):
                if minLen > right - left + 1:
                    minLen = right - left + 1
                    res = s[left : right + 1]
                scount[s[left]] -= 1
                if s[left] in tcount and scount[s[left]] < tcount[s[left]]:
                    cnt -= 1
                left += 1
            right += 1
        return res

一种稍微简单的方法，增减对T字符串统计用的字典的词频的方式，可以省略对S切片中元素个数的维护，也省去了中间的一大堆判断。

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        res = ""
        left, cnt, minLen = 0, 0, float('inf')
        count = collections.Counter(t)
        for i, c in enumerate(s):
            count[c] -= 1
            if count[c] >= 0:
                cnt += 1
            while cnt == len(t):
                if minLen > i - left + 1:
                    minLen = i - left + 1
                    res = s[left : i + 1]
                count[s[left]] += 1
                if count[s[left]] > 0:
                    cnt -= 1
                left += 1
        return res

参考资料：

https://leetcode.com/articles/minimum-window-substring/
http://www.cnblogs.com/grandyang/p/4340948.html

日期

2018 年 10 月 3 日 —— 玩游戏导致没睡好，脑子是浆糊。