[刷题防痴呆] 0438 - 找到字符串中的所有字母异位词 (F

题目地址

https://leetcode.com/problems/find-all-anagrams-in-a-string/

题目描述

438. Find All Anagrams in a String

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.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

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

思路

• 滑动窗口.
• init pCount.
• 对于字符串s, right每次右移, 然后看对应的s和p的right位置的count. 如果sCount大于pCount. left右移.
• 找到的right - left + 1 == p.length(). left为一个答案的起点.

关键点

代码

• 语言支持：Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
        }

        for (int left = 0, right = 0; right < s.length(); right++) {
            sCount[s.charAt(right) - 'a']++;
            while (sCount[s.charAt(right) - 'a'] > pCount[s.charAt(right) - 'a']) {
                sCount[s.charAt(left) - 'a']--;
                left++;
            }
            if (right - left + 1 == p.length()) {
                res.add(left);
            }
        }

        return res;
    }   
}