Sword finger offer II 015 All modifiers in the string

Summary

Advance of the previous question , It's still a double pointer + Hash table solution , Just don't stop this time .

subject

link ：https://leetcode.cn/problems/VabMRr

Given two strings s and p, find s All in p Of A modifier The string of , Returns the starting index of these substrings . Regardless of the order of the answer output .

A modifier Means the same letters , But arrange different strings .

Ideas

Advance of the previous question , Because you want to find multiple substrings . So on the basis of the previous question , Do not return directly when the first substring is found , Instead, record the starting index , Then the double pointer continues to move to the right .

solution ： Double pointer + Hashtable

Code

public List<Integer> findAnagrams(String s, String p) {
    
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) {
    
        return result;
    }

    int[] counts = new int[26];
    for (int i = 0; i < p.length(); i++) {
    
        counts[p.charAt(i) - 'a'] += 1;
        counts[s.charAt(i) - 'a'] -= 1;
    }
    if (allZero(counts)) {
    
        result.add(0);
    }

    for (int i = p.length(); i < s.length(); i++) {
    
        counts[s.charAt(i) - 'a'] -= 1;
        counts[s.charAt(i-p.length()) - 'a'] += 1;
        if (allZero(counts)) {
    
            result.add(i - p.length() + 1);
        }
    }

    return result;

}

public boolean allZero(int[] counts){
    
    for (int count : counts) {
    
        if (count != 0) {
    
            return false;
        }
    }
    return true;
}