438 Find All Anagrams in a Strin

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：

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".

解释下题目：

判断一个字符串里anagram的个数。

1. 老老实实判断

实际耗时：856ms

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i <= s.length() - p.length(); i++) {
        String tmp = s.substring(i, i + p.length());
        if (isAnagram(tmp, p)) {
            res.add(i);
        }
    }
    return res;
}

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        //长度都不相同还怎么可能是
        return false;
    }
    int[] arr = new int[26];

    for (int i = 0; i < s.length(); i++) {
        arr[s.charAt(i) - 'a']++;
        arr[t.charAt(i) - 'a']--;
    }
    for (int i = 0; i < s.length(); i++) {
        if (arr[s.charAt(i) - 'a'] != 0) {
            return false;
        }
    }

    return true;
}

  思路不说了，简单粗暴。

时间复杂度O(n*m) n为s的长度，m为p的长度。

空间复杂度O(1)

2. 滑动窗口

实际耗时：8ms

public List<Integer> findAnagrams2(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s == null || s.length() == 0 || p == null || p.length() == 0) return res;
    int[] table = new int[256];
    for (char c : p.toCharArray()) {
        table[c]++;
    }
    int left = 0, right = 0, count = 0;
    while (right < s.length()) {
        if (table[s.charAt(right)] > 0) {
            count++;
        }
        table[s.charAt(right)]--;
        right++;

        if (count == p.length()) {
            res.add(left);
        }

        if (right - left == p.length()) {
            if (table[s.charAt(left)] >= 0) {
                count--;
            }
            table[s.charAt(left)]++;
            left++;
        }

    }
    return res;
}

  其实一说滑动窗口就差不多都明白了，省力在如果p很长的情况下，有一大部分其实是可以省略判断的，有点像动态规划，所以那么省。需要注意的是，滑动窗口往右边移动的时候，如果划入窗口的那个字母不存在于table中，还是需要减一的，也就是table中的元素可能是负的，这一点我当时没想通，导致左边滑入的时候count无法做判断，想了半天。

时间复杂度O(n)

空间复杂度O(1)