Anagram of 2 words

Question

I am practicing java and some algorithms so I wanted to create a program to see if 2 words are anagrams of each other. My method was to use a quicksort to sort the words and then see if they matched. I tested me quicksort function and it seemed to work. Perhaps my anagram function is wrong? I tested my code against "tac" and "cat" and I am getting false.

Could someone take a look at my code and see where I went wrong?

my code:

public static boolean anagram(String s, String t) {
    int lenS = s.length();
    int lenT = t.length();
    if (lenS != lenT) {
        return false;
    }
    else if (quicksort(s) == quicksort(t)) {
            return true;
    }
    else { return false;}
}

public static String quicksort(String s) {
    int len = s.length();
    int median = len/2;     //pivot point
    String sortedString;
    if (len < 2) {
        return s;
    }
    else {
        String str = s.replace(String.valueOf(s.charAt(median-1)), "");
        char pivot = s.charAt(median-1);
        String less = "";
        String greater = "";
        for (int i = 0; i < str.length(); i++) {
            char pointed = str.charAt(i);
            if (pointed <= pivot) {
                less += String.valueOf(pointed);
            }
            else {
                greater += String.valueOf(pointed);
            }
        }
        sortedString = quicksort(less) + pivot + quicksort(greater);
        return sortedString; 
    }
}

score 2 · Accepted Answer · edited May 23 '17 at 11:56

quicksort(s) == quicksort(t)

There lies your issue - you're comparing Strings with ==, not .equals()! You should never use == to compare strings, silly academic examples aside. It's a mainstay of bugs and unpredictable behaviour. Sometimes it will work, but most of the time it will not (see here for a deeper explanation on the topic, but in practice the rule with strings is just "always use equals(), never use ==.)

So given that, the condition in your if statement should be quicksort(s).equals(quicksort(t)).

As an aside, you could bypass your entire quicksort() method and just use Arrays.sort() instead (after calling toCharArray() on the string.) Generally it's always better to use library sorting rather than writing your own sorting method, though I'm aware there's homework assignments and suchlike where this is required!

score 1 · Answer 2 · answered Mar 17 '14 at 10:30

I've been thinking about using quicksort to solve anagrams and think I have a shortcut. If we process both words with a quicksort at the same time, we can compare the pivot index at each iteration. At the end of the day, we're trying to avoid completing the 2 quicksorts if possible. With this approach, we use the pivot index as a preview of the finished result.

For example on iteration 1, the pivot index of quicksort 1 ends up being at position 4 with a value of "a" and the pivot index of quicksort 2 ends up being at position 6 and value "c" we are unable to use shortcut (yet).

However, say on iteration 1, the pivot index of quicksort 1 ends up being at position 4 with a value of "c" and the pivot index of quicksort 2 ends up being at position 6 with a value of "a" then we can determine that they will not be anagrams.

We can continue to use this approach throughout the comparison for each iteration.

This should change the efficiency of the comparison from "2n log(n)" to "n log(n)/2" (400% performance boost).

Anagram of 2 words

2 Answers2