Optimizing Java Anagram checker (compare 2 strings)

An anagram is like a mix-up of the letters in a string:


pots is an anagram of stop


Wilma is an anagram of ilWma

I am going through the book Cracking the Coding Interview and in the basic string manipulation there's the problem:


write a method to check if two strings are anagrams of each other.

My method uses StringBuffer instead of String because you can .deleteCharAt(index) with StringBuffer/StringBuilder.

public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {

    for (int i=0; i<s1b.length(); ++i) {
        for (int j=0; j<s2b.length(); ++j) {

            if (s1b.charAt(i) == s2b.charAt(j)) {

                s1b.deleteCharAt(i);
                s2b.deleteCharAt(j);

                i=0;
                j=0;
            }
        }
    }

    if (s1b.equals(s2b)) {
        return true;
    } else
        return false;

}

I iterate over every character in s1b and if I find a matching char in s2b I delete them both from each string and restart the loop (set i and j to zero) because the length of the StringBuffer objects changes when you .deleteCharAt(index).

I have two questions:

• Should I use StringBuilder over StringBuffer (in Java)?

• How can I make this faster?

In regards to fasterness:

This method is good in that it doesn't require any additional space, but it sorta destroys the data as you're working on it. Are there any alternatives that I have overlooked that could potentially preserve the strings but still see if they are anagrams without using too much external storage (i.e. copies of the strings are not allowed -- as a challenge)?

And, if you can use any sort of storage space in addition to this, can one lower the time complexity to \$O(n)\$ (technically \$O(2n)\$) instead of \$O(n^2)\$?

Also, the above code might not compile because I just wrote it from scratch in here; sorry if it's bugg'd.

Start with a simple, easy to understand version. Try to reuse API functions.

import java.util.Arrays;
... 

public boolean areAnagrams(String s1, String s2) {
    char[] ch1 = s1.toCharArray();
    char[] ch2 = s2.toCharArray();
    Arrays.sort(ch1);
    Arrays.sort(ch2);
    return Arrays.equals(ch1,ch2);
}

Of course this is not the fastest way, but in 99% it is "good enough", and you can see what's going on. I would not even consider to juggle with things like deleted chars in StringBuilder if there were no serious performance problem.

StackExchange Code Review Q#1690, answer score: 28