Drew L. Facchiano Drew L. Facchiano - 4 months ago 24
Java Question

Best solution for an anagram check?

I’m going through a permutation/anagram problem and wanted input on the most efficient means of checking.
Now, I’m doing this in Java land, and as such there is a library for EVERYTHING including sorting.
The first means of checking if two string are anagrams of each other is to check length, sort them in some manner, then compare each index of said string. Code below:

private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
return false;
}

char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();


Arrays.sort(strArr);
str = new String(strArr);

Arrays.sort(pairArr);
pair = new String(pairArr);

for(int i = 0; i<str.length(); i++){
if(str.charAt(i) != pair.charAt(i)){
return false;
}
}
return true;
}


Alternatively, I figured it would be easier to check based on ascii value and avoid a check on every possible character. Code below:

private boolean validAnagram(String str, String pair) {
if(str.length() != pair.length()){
return false;
}

char[] strArr = str.toCharArray();
char[] pairArr = pair.toCharArray();



int strValue = 0;
int pairValue = 0;

for(int i =0; i < strArr.length; i++){
strValue+= (int) strArr[i];
pairValue+= (int) pairArr[i];
}

if(strValue != pairValue){
return false;
}
return true;
}


So, which is a better solution? I don’t know much about the sort that Arrays is giving me, however that’s the more common answer when I look around the old internets. Makes me wonder if I’m missing something.

Answer

There are several ways to check whether two strings are anagrams or not . Your question is , which one is better solution . Your first solution has sorting logic. Sorting has worst case complexity of (nlogn) . Your second logic is only using one loop which has complexity O(n) .

So out of this two , your second solution which is having only O(n) complexity will be a better solution than first one .

One possible solution :

private boolean checkAnagram(String stringOne , String stringTwo){
        char[] first = stringOne.toLowerCase().toCharArray(); 
        char[] second = stringTwo.toLowerCase().toCharArray();
        // if length of strings is not same 
        if (first.length != second.length)
            return false;
        int[] counts = new int[26]; 
        for (int i = 0; i < first.length; i++){
            counts[first[i]-97]++;  
            counts[second[i]-97]--;   
        }
        for (int i = 0; i<26; i++)
            if (counts[i] != 0)
                return false;
        return true;
    }

Comments