Interview Problem: Anagram Strings.

Problem:

Decide if two strings are anagrams or not.

Solution:
Here, first sort two strings in order, then compare one with another character by character.
Time complexity: O(nlgn); The main consuming is the sort function used for sorting.
Space complexity: O(c); constant possibly.
/**
 * Decide if two strings are anagrams or not.
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 3:30:10 PM
 */
public class Anagrams {

    /*
     * Using sort function to check if they have the arrays after they are both
     * sorted.
     */
    public boolean isAnagramsSorted(String a, String b) {
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        Arrays.sort(aArray);
        Arrays.sort(bArray);
        // if (aArray.length != bArray.length)
        // return false;
        // for (int i = 0; i < aArray.length; i++)
        // if (aArray[i] != bArray[i])
        // return false;
        // return true;
        return Arrays.equals(aArray, bArray);
    }
}

Alternate Solution:

Here, using a hash table to keep the record of each existing character in string a, and then check the occurrence of each characters in string b.
1st, If they share the same length.
2nd, Needs to check if the ith character exists in string b.
3rd, subtract the number from hash table for each existing character in string b, until it's zero already. Then return false for that value.
Time complexity: O(n); n is the length of strings.
Space complexity: O(n); n is the number of unique characters in the strings, it should be smaller than the length of string.

It just takes more time to program.

import java.util.Arrays;
import java.util.Hashtable;

/**
 * Decide if two strings are anagrams or not.
 */

/**
 * @author antonio081014
 * @since Nov 5, 2011, 3:30:10 PM
 */
public class Anagrams {

    /*
     * Check if they share the same characters with the same counts.
     */
    public boolean isAnagramsUnsorted(String a, String b) {
        if (a == null || b == null)
            return false;
        if (a.length() != b.length())
            return false;
        Hashtable<String, Integer> set = new Hashtable<String, Integer>();
        for (int i = 0; i < a.length(); i++) {
            Integer tmp = set.get("" + a.charAt(i));
            if (tmp == null) {
                set.put("" + a.charAt(i), 1);
            } else {
                set.put("" + a.charAt(i), tmp + 1);
            }
        }
        for (int i = 0; i < b.length(); i++) {
            Integer tmp = set.get("" + b.charAt(i));
            if (tmp == null)
                return false;
            if (tmp.intValue() == 0)
                return false;
            set.put("" + b.charAt(i), tmp - 1);
        }
        return true;
    }
}

Conclusion:

The second algorithm apparently takes fewer time than the first one, it could be a good choice if memory limit is not such critical, especially good for large data sets. Even if the characters in two large files needs to be compared, it could be a good choice, since generally the number unique characters must be much less than the number of characters in the file.