【LeetCode】438.找到字符串中所有字母异位词

找到字符串中所有字母异位词

题目描述：

        给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

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

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路分析：

依然是滑动窗口法

        根据题目要求，我们需要在字符串 s寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p的长度相同，所以我们可以在字符串 s中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

优化思路

        在上述方法的基础上，我们不再分别统计滑动窗口和字符串中每种字母的数量，而是统计滑动窗口和字符串 p中每种字母数量的差；并引入变量cnt来记录当前窗口与字符串 p中数量不同的字母的个数，并在滑动窗口的过程中维护它。

        在判断滑动窗口中每种字母的数量与字符串 p中每种字母的数量是否相同时，只需要判断cnt是否为零即可。

代码实现注解：

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer>res=new ArrayList<>();//定义一个一维数组记录字母在两个字符串中出现的差值//cnt[x] = 0  表示 s与p中字母x出现次数相同 都出现了n次//cnt[x] = n  表示 在s中字母x出现次数比p多 多出现了n次//cnt[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次int[]cnt=new int[26];//统计字符数量int n=p.length();int m=s.length();//如果目标字符长度大于原始字符长度，返回空数组if(n>m){return res;}//开始遍历数组，创造窗口滑块，p数组出现的字母数值加一，S数组出现的字母数字减一。//所以当cnt数组上的数值为0是代表在滑块中p和s出现该字母的频率一致for(int i=0;i<n-1;i++){cnt[p.charAt(i)-'a']++;cnt[s.charAt(i)-'a']--;}//将P字符串中的最后一个字母读入cnt中cnt[p.charAt(n-1)-'a']++;int l=0;//将S字符串中的n-1位置上的字母作为滑块的右边界//开始滑动窗口for(int r=n-1;r<m;r++){cnt[s.charAt(r)-'a']--;int o=0;//随着右边界的右移，判断新的右边界。如果cnt数组上的数值为0，那么o赋值为1for(int j=0;j<26;j++){o+=cnt[j]==0?1:0;}//说明s和p的同一个字母出现频率相等if(o==26){res.add(l);}//左边界向右移，缩小窗口cnt[s.charAt(l++)-'a']++;}return res;}
}