leetcode解题: Find All Anagrams in a String (438)

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

解法1：滑动窗口， O（N) Time

比较自然想到的是用一个hash来记录p中出现的字符个数，然后对于每一个字串去比较是否是一个p的anagram。但如果一个一个的字串比较的话，复杂度很高。
仔细想一想，每次向前挪一位的时候，我们只是更新了一个字符的信息，所以说一部分在hashtable中的信息还是可以用的。
那么我们可以运用滑动窗口的算法来保留已经得到的信息，每移动一格就更新一下hashtable中的信息。
具体的算法是这样的：
先遍历一遍p，记录每一个字符出现的次数并记录在hashtable中。
这里用的是滑动窗口的算法。用两个指针记录当前窗口的大小，

right指针不停的向右侧移动。如果right指向的字符出现次数>=1，则表示找到一个对应的字符，所剩下的字符-1。
right字符在hashtable中出现的次数-1（无论是否出现过，如果没有出现过，则数值为负值，便于区分是否是p中的字符）
right向右移动
判断count是否为0，如果是表明所有的字符都出现过，则left指向的起始点就是一个有效的起始点。
如果窗口大小已经大于p的大小，那么就需要移动左指针。首先看left指向的是否出现在p中（一定是》0的），如果是则count++
无论是否出现过，hash的值+1，表明这个值已经退回。

C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.empty() || p.empty() ) {
            return res;
        }
        vector<int> hash(26, 0);
        for (char c : p) {
            hash[c - 'a']+=1;
        }
        int left = 0, right = 0; int count = p.size();
        while (right < s.size()) {
            if (hash[s[right] - 'a'] >= 1) {
                --count;
            }
            hash[s[right] - 'a']-=1;
            ++right;
            if (count == 0) {
                res.push_back(left);
            }
            if (right - left == p.size()) {
                if (hash[s[left] - 'a'] >= 0) {
                    count++;
                }
                hash[s[left] - 'a']+=1;
                left++;
            }
        }
        return res;
    }
};

Java

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        if (p == null || s == null || p.length() == 0 || s.length() == 0) {
            return res;
        }
        int[] hash = new int[26];
        for (char ss: p.toCharArray()) {
            hash[ss - 'a']++;
        }
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            char cur = s.charAt(right);
            if (hash[cur - 'a'] > 0) {
                count--;
            }
            ++right;
            hash[cur - 'a']--;
            if (count == 0) {
                res.add(left);
            }
            if (right - left == p.length()) {
                if (hash[s.charAt(left) - 'a'] >= 0) {
                    ++count;
                }
                hash[s.charAt(left) - 'a']++;
                ++left;
            }
        }
        return res;
    }
}

运用滑动窗口的模板写一下
Java

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<Integer>();
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        int start = 0, end = 0;
        int count = map.size();
        while (end < s.length()) {
            char current = s.charAt(end);
            if (map.containsKey(current)) {
                map.put(current, map.get(current) - 1);
                if (map.get(current) == 0) {
                    count--;
                }
            }
            end++;
            while (count == 0) {
                // check if the current substring (start, end) qualify for a anagram
                if (end - start == p.length()) {
                    res.add(start);
                }
                char temp = s.charAt(start);
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                    if (map.get(temp) > 0) {
                        count++;
                    }
                }
                start++;
            }
        }
        return res;
    }
}

解法1： 滑动窗口， O（N) Time

解法1：滑动窗口， O（N) Time