438. Find All Anagrams in a Stri

文章源地址

算法介绍：

第一步

NumberOfDeference = p.length()，用来表示目前窗口中的字符和p的差异度（由于窗口最大时（为p.length()）才有可能使NumberOfDeference为0，所以NumberOfDeference 为0时窗口中与p为Anagrams）。NumberOfDeference差异度的含义：一开始窗口左右指针都指向第一个，所以差异度最大为p.length()；当窗口中进来一个p中有的字符，差异度就减一，出去一个有的差异度就增一；至于进来或出去的是p中没有的则NumberOfDeference不变，反正窗口的最大值也不过是p.length()。

第二步

窗口的左右两个指针：left和right，分别指向窗口的左端和右端。

滑动窗口具体操作：

1. 先滑动右指针:
   1. 加进来的字符如果该字符在数组asciiChars的计数中非负，则NumberOfDeference减一，否则不做操作
   2. 无论在不在数组asciiChars该字符相应位置计数都减一
   3. 如果滑动完right，判断如果窗口长度到达p.length()（如果长度到达p.length()，并且NumberOfDeference为0，则将此时的left值加入到result中），滑动左窗口。
2. 滑动左指针：
   1. 被踢出窗口的那个字符如果在数组asciiChars的计数中非负，则NumberOfDeference增一，不在则不做操作。
   2. 无论在不在数组asciiChars该字符相应位置计数都加一

第三步

上面1.1和2.1操作的原理：asciiChars中的记录的数据是代表p中含有的的每个字符的数量去掉当前窗口中存在的p字符串中每个字符的数量，一开始窗口大小为0，啥都不存在，自然asciiChars中记录的就是全部p中含有的的每个字符的数量，如果窗口中有一个，则asciiChars相应的记录中就少一个。如果窗口中多包含一个p中没有的（或者包含的某一个字符的数量比p中有的还多），那么这时候，asciiChars中相应的记录值就会变成负数，代表当前窗口中包含相应字符的“多余”的数量。

所以当进来一个的时候，如果相应记录为非负，那么这个进入是有意义的，则差异度（NumberOfDeference）减一；当出去一个的时候，如果相应记录为非负，那么这个出去是有意义的，则差异度（NumberOfDeference）加一。

第四步

asciiChars用到哈希表思想，用来记录p中每一种字符分别有多少个。详见《如何判断两个String是否是Anagrams》一文。

public static List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<Integer>();
    int NumberOfDeference = p.length();  //差异度指数
    int left=0,right=0;  //窗口左右指针
    int[] asciiChars = new int[256];  
    //记录p中字符有哪些及其数量的数组
    for (int i = p.length() - 1; i>=0; --i){
        ++asciiChars[p.charAt(i)];
    }
    //滑动右窗口
    for(;right<s.length();right++){
        asciiChars[s.charAt(right)]--;  //在该字符相应位置减一
        if(asciiChars[s.charAt(right)]>=0)
        NumberOfDeference--; //如果加进来的那个在p中，NumberOfDeference减一
        if(right-left == (p.length()-1)){
            //如果这时窗口大小为p.length()
            if(NumberOfDeference==0){
                result.add(left); //这时出现一次匹配，将左窗口加到result中
            }
            //下面是滑动左窗口的操作
            if(asciiChars[s.charAt(left)]>=0) {
                NumberOfDeference++; //如果被踢出的那个在p中，NumberOfDeference加一
            }
            asciiChars[s.charAt(left)]++;//数组中相应字符计数位置加回来
            left++; //左窗口向右滑动
        }
    }
    return result;
}

from collections import Counter
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        p_c = Counter(p)
        left, right, count = 0, 0, len(p)
        ret = []
        while right<len(s):
            p_c[s[right]] -= 1
            if p_c[s[right]] >=0:
                count -= 1
            if right-left == len(p)-1:
                if count == 0:
                    ret.append(left)
                if p_c[s[left]] >=0:
                    count += 1
                p_c[s[left]] += 1
                left += 1
            right += 1
        print ret