题目
给定两个字符串 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” 的变位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
分析
和14题差不多，
坑：
1、边界判断
2、不该return的时候不要return
3、
// 使用双指针
public List<Integer> findAnagrams(String s, String p) {
// 定义返回结果
List<Integer> list = new ArrayList<>();
// 定义结果集
int[] counts = new int[26];
// 边界判断
if(p.length()>s.length()){
return list;
}
// 将p都放到结果集中，将s的前p.length()放到结果集中
for(int i=0; i<p.length(); i++){
counts[p.charAt(i)-'a']++;
counts[s.charAt(i)-'a']--;
}
// 直接判断
if(allZero(counts)){
System.out.print("----");
list.add(0);
}
// 使用双指针（滑动窗口）
for(int j=p.length(); j<s.length(); j++){
counts[s.charAt(j)-'a']--;
counts[s.charAt(j-p.length())-'a']++;
if(allZero(counts)){
list.add(j-p.length()+1);
}
}
return list;
}
private static boolean allZero(int[] counts){
for(int i=0;i<counts.length;i++){
if(counts[i]!=0){
return false;
}
}
return true;
}
二刷
变位词的特点，没对变位词中单词出现的次数是一样的----因此可以使用数组来保持出现的次数+双指针
class Solution {
// 变位词特点：长度和其中单词出现的次数相同
// 解法，使用双指针和hash表的方式解决
public List<Integer> findAnagrams(String s, String p) {
// 定义返回结果，返回初始索引的集合
List<Integer> result = new ArrayList<>();
// 定义每个单词出现的次数
int[] counts = new int[26];
// 极端判断
if(s.length() < p.length()){
return result;
}
// 将p和s的前几个的结果优先存放到记录出现次数的集合中
for(int i = 0; i < p.length(); i++){
// 通过减a的方式来确定下标位置
counts[p.charAt(i) - 'a']++;
counts[s.charAt(i) - 'a']--;
}
// 节约了前面的第一次判断，这里可以直接判断一次
if(allZero(counts)){
// 第一个索引位置是0
result.add(0);
}
// 使用双指针去判断剩下的str
for(int j = p.length(); j < s.length(); j++){
// 后一个位置的值需要--
counts[s.charAt(j) - 'a'] --;
// 前一个位置的值需要++（因为前面一开始是-掉的,从头上移动）
counts[s.charAt(j - p.length()) - 'a'] ++;
if(allZero(counts)){
result.add(j - p.length() + 1);
}
}
return result;
}
/**
判断存放出现次数的数组中是否都是零，都是零的话说明有一组变位词
*/
private boolean allZero(int[] counts){
for(int count : counts){
if(count != 0){
return false;
}
}
return true;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96211.html
