Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
这道题目看似简单，里面玄机非常多，建议手写试试
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
int l = p.length();
int x=0;
int[] chars = new int[26];
List result = new ArrayList();
for(int i=0;i<p.length();i++){
chars[p.charAt(i) - 'a'] ++;
}
while(x<s.length()){
int count=0;
int[] cp = chars.clone();
if(chars[s.charAt(x) - 'a'] != 0 && x+l<=s.length()){
count ++;
int tmp = 1;
cp[s.charAt(x) - 'a']--;
while(tmp<l){
if(cp[s.charAt(x+tmp) - 'a'] > 0){
cp[s.charAt(x+tmp) - 'a']--;
count++;
}
tmp++;
}
if(count == l){
result.add(x);
}
}
x++;
}
return result;
}
}
微信扫一扫
支付宝扫一扫
