1、题目要求
给定两个字符串?s?和 p，找到?s?中所有?p?的?异位词?的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例：
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
2、避坑
?他要求“相同的字符串”也算异位词，我一开始就没看到，导致好多测试样例过不去...
例如：
输入：s="abb",p="bb"
输出: [1]
3、代码实现
public List<Integer> findAnagrams(String s, String p) {
//记录p串里各个字母有多少个
int[] numberP = new int[26];
int[] tempP = new int[26];
int b;
List<Integer> orderList = new ArrayList<>();
for(int i=0;i<p.length();i++){
//记录数组中对应位置的值+1
numberP[p.charAt(i)-'a']++;
}
for(int i=0;i<=s.length()-p.length();i++){
String m = s.substring(i,i+p.length());
for(int j=0;j<m.length();j++){
char x = m.charAt(j);
tempP[x-'a']++;
}
for(b=0;b<26;b++){
if(tempP[b]!=numberP[b]){
break;
}
}
if(b==26){
//遍历全部完成，说明暂存数组记录下来的p字符串每个字母出现的次数和原数组完全一致
//就把开头字符的序号存入list集合
orderList.add(i);
}
//重置暂存数组
tempP=new int[26];
}
return orderList;
}
?
|