Sort an array of strings so that anagrams are next to each other

Write a method to sort an array of strings so that all the anagrams are next to each other.

My initial thoughts:
Do a bubble-sort kind sort. Check if two pairs of strings are anagrams or not, if yes, swap.

My initial codes:

	private static boolean areAnagrams(String s1, String s2) {
		if (s1.length() != s2.length() || s1 == null || s2 == null)
			return false;
		s1 = s1.toLowerCase();
		s2 = s2.toLowerCase();
		int[] table = new int[26];
		for (int i = 0; i < s1.length(); ++i) {
			int index = s1.charAt(i) - 'a';
			table[index]++;
		}
		for (int i = 0; i < s2.length(); ++i) {
			int index = s2.charAt(i) - 'a';
			if (table[index] <= 0)
				return false;
			table[index]--;
		}
		for (int i = 0; i < 26; ++i) {
			if (table[i] > 0)
				return false;
		}
		return true;
	}

	private static void swap(String[] strings, int i, int j) {
		String temp = strings[i];
		strings[i] = strings[j];
		strings[j] = temp;
	}

	public static void sortAnagrams(String[] strings) {
		for (int i = 0; i < strings.length - 1; ++i) {
			for (int j = i + 1; j < strings.length; ++j) {
				if (areAnagrams(strings[i], strings[j]))
					swap(strings, i + 1, j);
			}
		}
	}

Comments after running:
It does not guarantee the alphabetical orderings of strings:

  • INPUT: “xyz”, “ca”, “ab”, “ac”, “ba”, “zyx”
  • EXPECTED OUTPUT: “ab”, “ba”, “ac”, “ca”, “xyz”, “zyx”
  • ACTUAL OUTPUT: “xyz”, “zyx”, “ab”, “ba”, “ac”, “ca”

Solution:

	public class AnagramComparator implements Comparator<String> {
		public String sortChars(String s) {
			char[] content = s.toCharArray();
			Arrays.sort(content);
			return new String(content);
		}

		public int compare(String s1, String s2) {
			return sortChars(s1).compareTo(sortChars(s2));
		}
	}

	public static void main(String[] args) {
		String[] strings = { "xyz", "ca", "ab", "ac", "ba", "zyx" };
		AnagramComparator comparator = new AnagramComparator();
		Arrays.sort(strings, comparator);
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: