LeetCode Hot之七：438. 找到字符串中所有字母异位词

news/2025/3/29 4:23:07/

题目：

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

思路

哈希加滑动窗口。构造两个数组scnt和pcnt，分别存储s和p的字符在26个字母中的映射。如果这两个数组相等，那么就说明是字母异位词。且scnt和pcnt的长度也应该一致，因为scnt会同时作为滑动窗口。

代码

以下代码来自“德莫夫先生”在力扣上的对于官方代码的注释，讲解的很细致。

    int sLen=s.length();int pLen=p.length();if(sLen<pLen){return ans;}//建立两个数组存放字符串中字母出现的词频，并以此作为标准比较int [] scount=new int[26];int [] pcount=new int[26];//当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）for(int i=0;i<pLen;i++){++scount[s.charAt(i)-'a']; //记录s中前pLen个字母的词频++pcount[p.charAt(i)-'a']; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)}//判断放置处是否有异位词     (在放置时只需判断一次)if(Arrays.equals(scount,pcount)){ans.add(0);}   //开始让窗口进行滑动for(int i=0;i<sLen-pLen;i++){ //i是滑动前的首位--scount[s.charAt(i) -'a'];       //将滑动前首位的词频删去++scount[s.charAt(i+pLen) -'a'];  //增加滑动后最后一位的词频（以此达到滑动的效果）//判断滑动后处，是否有异位词if(Arrays.equals(scount,pcount)){ans.add(i+1);} }return ans;
}