438. Find All Anagrams in a String - Medium

前往題目

之前寫的文章

想法

• 用map
• 用Sliding window

思路

1. 備用array來儲存sliding window的資訊，另一個array用來儲存p的counts
2. 開始疊代s，每次循環都看看是否和p array相等，超過p的長度時就開始把p長度之前的字母去掉，以保證window的size和p的length一樣
3. 遇到array相等就加第一個字母的index到結果中

Code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        // Array to count s
        int[] S = new int[26];

        // Array to count p
        int[] P = new int[26];
        
        // Store p's character count
        for (char c : p.toCharArray()) {
            P[c - 'a']++;
        }

        for (int i = 0; i < s.length(); ++i) {
            // Count s's char
            S[s.charAt(i) - 'a']++;

            // Maintain the window size of s segment as large as p
            // 這一步是保證window和p的size一樣，例如p是"abc"那size就是3，當i為2的時候不會符合條件，3的時候才會，這時window的size就是4了，所以要把頭去掉
            if (i >= p.length()) {
                // Remove the head
                S[s.charAt(i - p.length()) - 'a']--;
            }

            // Compare
            if (Arrays.equals(S, P)) {
                res.add(i - p.length() + 1);
            }
        }

        return res;
    }
}