力扣-找到字符串中所有字母异构词-438

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

我们可以考虑使用左右指针，在字符串s上放置一个滑动窗口，窗口的长度刚好等于非空字符串p的长度。然后判断滑动窗口内的子串是否等于非空字符串p的全排列中的某一种。具体判断的方法，可以用两个数组sArr和pArr，下表字符，值表示出现的次数，类似于一个Map，但是在代码中我们可以简单用一个数组维护。具体代码如下：

package LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode438 {
    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        
        Solution_LeetCode438 ans = new Solution_LeetCode438();
        List<Integer> res = ans.findAnagrams(s, p);
        
        for(int i = 0; i < res.size(); i++) {
            System.out.println("第" + i +"个索引" + res.get(i));
        }
    }
}

class Solution_LeetCode438 {
    public List<Integer> findAnagrams(String s, String p) {
        if(s == null || p == null || s.length() < p.length()) return new ArrayList<Integer>();
        
        List<Integer> res = new ArrayList<Integer>();
        
        int[] sArr = new int[26];
        int[] pArr = new int[26];
        
        for(int i = 0; i < p.length(); i++) {    //统计字符出现的次数
            sArr[s.charAt(i)-'a'] += 1;
            pArr[p.charAt(i)-'a'] += 1;
        }
        
        int i = 0, j = p.length();//i是滑动窗口的起始位置，j是滑动窗口的最后位置的下一个位置
        
        while(j < s.length()) {
            if(isSame(sArr, pArr)){
                res.add(i);
            }
            //滑动窗口
            sArr[s.charAt(i)-'a']--; i+=1;
            sArr[s.charAt(j)-'a']++; j+=1;
        }
        
        if(isSame(sArr, pArr)){
            res.add(i);
        }
         
        return res;
    }
    
    public boolean isSame(int[] sArr, int[] pArr) {
        for(int i = 0; i < sArr.length; i++) {
            if(sArr[i] != pArr[i]) {
                return false;
            }
        }
        return true;
    }
}

力扣-找到字符串中所有字母异构词-438

推荐阅读