Substring with Concatenation of All Words

这道题主要是对于子字符串是否满足要求进行检查是一个难点，另外需要考虑words里的总长度比s还要大的情况，因为words中的每个词都是一样长，所以检查子字符串的算法就相对好写，不然这个算法很难实现

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not words:
            return []

        counts = {}
        for word in words:
            counts.setdefault(word, 0)
            counts[word] += 1

        n = len(s)
        step = len(words[0])
        m = len(words) * step
        cur, fast = 0, m

        if m > n:
            return []
        tmp = s[cur : fast]
        res = []

        while cur < n:
            while fast < n and fast - cur < m:
                tmp += s[fast]
                fast += 1

            tmp_dict = copy.copy(counts)
            if self.check(tmp, tmp_dict, step):
                res.append(cur)
            cur += 1
            tmp = tmp[1:]

            if fast == n:
                break

        return res

    def check(self, string, checker, step):
        n = len(string)
        for i in xrange(0, n, step):
            if string[i : i + step] in checker:
                checker[string[i : i + step]] -= 1
                if checker[string[i : i + step]] < 0:
                    return False
            else:
                return False
            if i + step > n:
                return False
        return True