Minimum Window Substring

这道题是一个非常好理解的双指针加哈希表类型的题目，不过需要稍微注意一下边界问题，另外如果一开始采用的策略是每移动一次指针都要对两个哈希表进行检查的话，此题虽然能AC但是时间表现很差几乎是压线过了

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        from collections import Counter

        n, m = len(s), len(t)
        sCounter = Counter()
        tCounter = Counter(t)
        cur = 0
        minLength = sys.maxint
        result = ''

        for i in xrange(n - m + 1):
            while cur < n and not check(sCounter, tCounter):
                if s[cur] in sCounter:
                    sCounter[s[cur]] += 1
                else:
                    sCounter[s[cur]] = 1
                cur += 1

            if cur - i < minLength and check(sCounter, tCounter):
                minLength = cur - i
                result = s[i : cur]

            sCounter[s[i]] -= 1

        return result

def check(strCounter, targetCounter):
    for key, value in targetCounter.items():
        if key not in strCounter or strCounter[key] < value:
            return False

    return True

这里需要注意cur超界的情况

因为时间表现不好，这里最容易首先想到的优化方法就是将哈希表变成ASCII数组来减少时间

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        n, m = len(s), len(t)
        if m > n:
            return ''

        sCounter = [0] * 256
        tCounter = [0] * 256
        minLength = sys.maxint
        result = ''
        for i in xrange(m):
            sCounter[ord(s[i])] += 1
            tCounter[ord(t[i])] += 1

        cur = m
        for i in xrange(n - m + 1):
            while cur < n and not check(sCounter, tCounter):
                sCounter[ord(s[cur])] += 1
                cur += 1

            if cur - i < minLength and check(sCounter, tCounter):
                minLength = cur - i
                result = s[i : cur]

            sCounter[ord(s[i])] -= 1

        return result

def check(strCounter, targetCounter):
    for i in xrange(256):
        if targetCounter[i] > strCounter[i]:
            return False

    return True

照道理讲这样用数组的检查应该比纯哈希表更快，但是这里更慢了，不过可以作为一个空间优化的答案，常数级别的数组总是比哈希表要强的，九章还有一种应该更优化的做法暂时还没有懂