Find All Anagrams in a String

此题可以每次对长度为len(p)的子字符串进行排序然后用这个子字符串和p进行比对，这种逻辑是正确的，时间复杂度为O(nl)，对于大数据是无法AC的，其实这道题的解决思路和普通的字符串匹配非常类似，我们需要做的并不是一定要把时间复杂度真正的降下去，类比字符串匹配中的RabinKarp算法也不是真正把时间复杂度降到了O(n)而只是通过哈希把一些不需要判断的情况筛去从而降低了O(nl)复杂度的时间常数，这里的基本思维也是和RabinKarp一样利用哈希后的哈希表来进行比对从而通过大数据检测

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        from collections import Counter

        n, m = len(s), len(p)
        sCounter = Counter(s[:m])
        pCounter = Counter(p)
        res = []

        for i in xrange(n - m + 1):
            if self.check(sCounter, pCounter):
                res.append(i - m)

            sCounter[s[i]] -= 1
            sCounter[s[i + m]] += 1

        return res

    def check(self, aCounter, bCounter):
        for key in bCounter:
            if key not in aCounter or aCounter[key] != bCounter[key]:
                return False

        return True

上面代码实际上的时间复杂度还是O(nl)，但是我们可以通过更加准确的优化来进一步把时间复杂度真正降至O(n)，首先因为输入的字符串都是ASCII码，我们实际上可以通过256长度的数组更加精确且节省空间的实现哈希表的功能，另外因为对于p的字符计数是不变的，我们这里又可以通过RabinKarp的思维提前先算好对应的数据，每次移动窗口的时候我们就只需要对其中的一个位置进行改变实现O(1)的比对了，这就实现了真正将时间复杂度降至O(1)

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        count = [0] * 256
        n = len(s)
        m = len(p)

        if m > n:
            return []

        for i in xrange(m):
            count[ord(s[i])] += 1
            count[ord(p[i])] -= 1

        absSum = 0
        for num in count:
            absSum += abs(num)

        result = []
        if absSum == 0:
            result.append(0)

        for i in xrange(n - m + 1):
            if i < n - m:
                absSum -= (abs(count[ord(s[i])]) + abs(count[ord(s[i + m])]))
                count[ord(s[i])] -= 1
                count[ord(s[i + m])] += 1
                absSum += (abs(count[ord(s[i])]) + abs(count[ord(s[i + m])]))
                if absSum == 0:
                    result.append(i + 1)

        return result