source: https://leetcode.com/problems/find-all-anagrams-in-a-string/description/
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
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".
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public List<Integer> findAnagrams(String s, String p) { //create a freqency of string p int[] freqP = new int[26]; char[] pArr = p.toCharArray(); for(char c: pArr){ freqP[c-'a']++; } int[] freqS = new int[26]; char[] sArr = s.toCharArray(); int lo = 0; //to store the result List<Integer> list = new ArrayList<>(); for(int hi=0;hi<sArr.length;hi++){ freqS[sArr[hi]-'a']++; //if the diff between hi and lo is greater than the length of string p //then shift the window if((hi-lo)+1>pArr.length){ freqS[sArr[lo]-'a']--; lo++; } //if the diff between hi and lo is equals to the length of string p //then compare the frequency map of string p and window if((hi-lo)+1==pArr.length){ if(compare(freqS, freqP)){ list.add(lo); } } } return list; } private boolean compare(int[] freq1, int[] freq2){ for(int i=0;i<26;i++){ if(freq1[i]!=freq2[i]){ return false; } } return true; } } |