Tuesday, August 4, 2015

check if one string has anagram substring of the other string

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