题目大意：
找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 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" 的字母异位词。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=438
解题思路分析：
看到求字符串区间的题目我们应该下意识想到使用双指针（或者滑动窗口）来解题。这里说句题外话，Leetcode中大部分题目实际上都存在着一定的解题套路，一般情况下我们看到某些条件或者某些关键字时，就应该马上联想到使用什么思路来破解。比如看到树形结构时应联想到dfs或者bfs；看到返回结果会很大时（例如需要对10^9+7取模）应马上意识到这很可能是动态规划的题目；再比如本题这种求子串或者子数组类型的问题，首先要想到双指针等等。一直以来都想总结一篇关于leetcode中解题套路的文章，但碍于时间原因一直没能着手（残念）。
回到本题，由于题目求的是异位词子串，因此单单比较子串是否相同是行不通的，这种情况下我们通常需要对字符串进行预处理，即统计出它包含的每一种字符的个数。因此解题时，我们需要先统计出字符串p中每一种字符的个数。然后再使用双指针思路，找出s中的合理区间子串（该子串包含的字符种类和个数与p中的元素相同）。
对于双指针思路，我们需要定义左右两个指针变量，初始时都在下标0的位置。左右指针所包含的区间即是当前子串范围。开始时，我们首先尝试向右移动1位右指针（扩大范围），右指针当前指向的字符即是范围扩大后新加入进来的字符，我们查看该字符在p中的个数，这时存在三种情况：
- 如果p中不存在该字符（个数为0），说明s中包含当前字符的区间都是不合理区间，我们将左右指针同时移动到当前位置的下一位。
- 如果当前区间内该字符个数小于p中该字符个数，说明当前区间内的字符个数还没到达p中的水平，可将当前区间内当前字符个数加一。加一操作后，查看当前区间内所有字符个数是否与p中相同，如果相同的话，当前区间是一个合理区间，返回结果加一。
- 如果当前区间内该字符个数等于p中该字符个数，说明当前区间内该字符个数已满，再加上当前字符的话会超出p中相应的个数（多一个），此时应当尝试向右移动左指针（缩小区间范围），同时左指针对应字符在区间内的个数减一。直到区间内右指针的字符个数等于p中相应个数（不再多一个）为止，此时依旧需要查看当前区间内所有字符个数是否与p中相同，如果相同的话，当前区间是一个合理区间，返回结果加一。
实现代码：
public List<Integer> findAnagrams(String s, String p) {
// 统计p中每种字符个数
int[] pCount = new int[26];
for(char c : p.toCharArray()){
pCount[c-'a']++;
}
// s中当前区间内每种字符个数
int[] sCount = new int[26];
// 返回结果
List<Integer> res = new ArrayList<>();
// 左指针
int left=0;
// 循环右指针
for(int right=0;right<s.length();right++){
// 当前字符
int c=s.charAt(right)-'a';
if(pCount[c]==0){ // 当前字符在p中不存在
left=right+1;
sCount = new int[26];
continue;
}else if(sCount[c]<pCount[c]){ // 当前字符个数小于p中相应个数
sCount[c]++;
if(sCount[c]==pCount[c]&&isSame(sCount,pCount)){
res.add(left);
}
}else if(sCount[c]==pCount[c]){ // 当前字符个数等于p中相应个数
sCount[c]++;
while(left<right){
int lc=s.charAt(left)-'a';
sCount[lc]--;
left++;
if(lc==c) {
if(isSame(sCount,pCount)){
res.add(left);
}
break;
}
}
}
}
return res;
}
boolean isSame(int[] sCount, int[] pCount){
for(int i=0;i<26;i++){
if(pCount[i]!=sCount[i]) return false;
}
return true;
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 85.80% of Java online submissions for Find All Anagrams in a String.
Memory Usage: 40.6 MB, less than 14.00% of Java online submissions for Find All Anagrams in a String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-438-find-all-anagrams-in-a-string-解题思路分析/
View Comments (0)