Find All Anagrams in a String
给两个字符串s和p, 找出p在s中所有的anagram.
但凡是anagram基本都是用counting, 这个题也是, 因为已知p的长度, 所以用两个指针即可扫描所有可能的substring, 然后找出anagram即可, 找anagram用hash.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public List<Integer> findAnagrams(String s, String p) { int[] count = new int[26]; List<Integer> res = new ArrayList<>(); for(char c : p.toCharArray()) count[c - 'a']++; int h = hash(count); int[] count_s = new int[26]; int n = p.length(); for(int i = 0; i < s.length(); i++) { if(i > n - 1) count_s[s.charAt(i - n) - 'a']--; count_s[s.charAt(i) - 'a']++; if(h == hash(count_s)) res.add(i-n+1); } return res; } public int hash(int[] nums) { int h = 0; int p = 31; int mod = 100001; for(int i = 0; i < nums.length; i++) { h += ((h * p) + nums[i]) % mod; } return h; } } |