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; } }