找到字符串中的异位词

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @param p string字符串
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/9ff491c910e5427fab6ae67745929085?tpId=196&tqId=40518&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        1. 使用pNums[26]，统计字符串p中每个字符出现次数
        2. 滑动窗口法，窗口大小为[left, right], right - left = len(p)，初始left = 0, right = len(p) - 1, 使用sNums[26]统计窗口内字符出现次数，如果pNums = sNums，将left加入结果res中，移动窗口，知道right = len(s)结束
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(1)
    """

    def findWord(self, s, p):
        # write code here
        n, m = len(s), len(p)
        pNums, sNums = [0] * 26, [0] * 26

        for i in range(m):
            pNums[ord(p[i]) - ord("a")] += 1
            sNums[ord(s[i]) - ord("a")] += 1

        res = []
        left, right = 0, m - 1
        while right < n:
            if sNums == pNums:
                res.append(left)
            sNums[ord(s[left]) - ord("a")] -= 1
            left += 1
            right += 1
            if right < n:
                sNums[ord(s[right]) - ord("a")] += 1
        return res


if __name__ == "__main__":
    sol = Solution()

    # s, p = "cabac", "abc"

    s, p = "ababab", "ab"

    res = sol.findWord(s, p)

    print res