438. Find All Anagrams in a String

难度: Medium

题目描述

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

 

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

 

Constraints:

• 1 <= s.length, p.length <= 3 * 104
• s and p consist of lowercase English letters.

解题思路

代码实现

解决方案

java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        int pLen = p.length();
        int sLen = s.length();
        int left = 0;
        List<Integer> res = new ArrayList<>();
        int[] pCharCount = new int[26];
        for (int i = 0; i < pLen; i++) {
            char c = p.charAt(i);
            pCharCount[c - 'a']++;
        }
        int[] compareCharCount = new int[26];
        for (int right = 0; right < sLen; right++) {
            char c = s.charAt(right);
            compareCharCount[c - 'a']++;
            if (right - left + 1 == pLen) {
                if (compareArray(pCharCount, compareCharCount)) {
                    res.add(left);
                }
                char leftC = s.charAt(left);
                compareCharCount[leftC-'a']--;
                left++;
            }


        }

        return res;

    }

    boolean compareArray(int[] a, int[] b) {
        for (int i = 0; i < 26; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }
}