2
\$\begingroup\$

I'm writing a program to check whether a pair of Strings (entered by the user) are anagrams. I've already did with the standard way to sort both of the strings using Arrays.sort() but I also thought of an alternative version not requiring any sorting and ended up with this:

import java.util.Scanner;

public class Anagrams {
    public static void main(String[] args) {
        String s1, s2;
        try (Scanner sc = new Scanner(System.in)) {
            System.out.println("Enter the two words: ");
            s1 = sc.nextLine().toLowerCase().replace(" ", "");
            s2 = sc.nextLine().toLowerCase().replace(" ", "");
        }
        if (s1.length() == s2.length() && isAnagram(s1, s2)) {
            System.out.format("%s is an anagram of %s.", s1, s2);
        } else {
            System.out.format("'%s' and '%s' are not anagrams.", s1, s2);
        }
    }

    public static boolean isAnagram(String s1, String s2) {
        return (sumOfChars(s1) == sumOfChars(s2));
    }

    public static int sumOfChars(String s) {
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += c;
        }
        return sum;
    }
}

I know this isn't perfect but it does work with most of the anagram pairs that exist in the dictionary (that I've tested). Can I improve anything here or should I forgo this?

\$\endgroup\$
3
\$\begingroup\$

This wont ever work entirely correctly. What you did here can also be seen as calculating the hash of the 2 Strings. And just like you cannot use a hash to compare equality of 2 objects, you can't use your sumOfChars to compare if 2 strings are anagrams or not. (Simple counter example are the strings "ac" and "bb".)

On the other hand, that doesn't mean this idea is useless for exactly the same reasons as why we still provide a hashCode method when implementing equals.

If the 2 strings are more often NOT anagrams then they ARE anagrams, it can be a lot cheaper to first check if the sums are equal, and after that check for actual "anagram equality".

I suggest to update your isAnagram method to something like this:

public static boolean isAnagram(String s1, String s2) {
    if(s1.length() != s2.length() return false;
    if(sumOfChars(s1) != sumOfChars(s2)) return false;
    return sameLetterCount(s1, s2);
}

Notice that I also put the length() check in this method as well. The idea is actually the same. You start with a really cheap test that returns early in certain cases (strings of different length). Then you do a bit more expensive test that takes out most (but still not all) cases to return early again. When those tests didn't fail, you got some good candidates to do the expensive actual checking for containing the same letters.

I have written it in my example so that it calls a different method. But you might as well just implement some letter counting algorithm right after the 2 if checks.

\$\endgroup\$
2
  • \$\begingroup\$ Time complexity for this algo would be O(n+n) , O(n) for sumOfChars() and O(n) for sameLetterCount() . You can make it little more faster by droping sumOfChars() check (unnecessary to me), time complexity will become O(n) \$\endgroup\$ – snehm Jan 22 '18 at 13:20
  • \$\begingroup\$ O(n + n) = O(2n) = O(n). In the big O we ignore (most) constants. You are correct in that you don't really need the sameLetterCount to have a decent implementation of an anagram checker. What you gain by adding this check depends mostly on how the sameLetterCount is implemented. It's either lower memory cost, or a bit speed in most cases (but it's slower for actual anagrams or cases where the other implementation would be able to quit early on the first letters of the second word). \$\endgroup\$ – Imus Jan 23 '18 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.