Most of the anagram related question can be solved by using int array, each element in the array representing the number of appearances of each char in the string.
/*
* Given 2 strings, check if any one of them
* has any anagram of the other string, as a substring of it.
*
* here without losing generality s1.length() > s2.length()
*
* time complexity: O(L2) + O(L1)*O(1) = O(L1)
*/
public static boolean hasAnagramSubstring(String s1, String s2){
assert s1.length() > s2.length();
final int ALPHA_SIZE = 256;
int[] store2 = new int[ALPHA_SIZE];
for(char c : s2.toCharArray())
store2[c] ++;
char[] chars = s1.toCharArray();
int[] store1 = new int[ALPHA_SIZE];
for(int i=0; i<s2.length(); i++){
store1[chars[i]]++;
}
//count the number of different characters in each string
int numOfNonZero = 0;
for(int i=0; i<ALPHA_SIZE; i++){
//store the difference between two int array in store1
store1[i] = store1[i] - store2[i];
if(store1[i]!=0)
numOfNonZero++;
}
if(numOfNonZero==0)
return true;
for(int i = s2.length(); i<s1.length(); i++){
store1[chars[i]]++;
if(store1[chars[i]]==0)
numOfNonZero--;
store1[chars[i-1]]--;
if(store1[chars[i-1]]==0)
numOfNonZero--;
if(numOfNonZero==0)
return true;
}
return false;
}
No comments:
Post a Comment