Anagrams @LeetCode

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

	package leetcode;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.HashMap;
	/**
	* Solution: We need to find out all sub groups that are anagrams and then merge into a big group and return.
	* We use hashMap<count, ArrayList> to divide them into different groups and finally filter by ArrayList.size() > 1
	* The difficult part here is divide them into groups. HashMap achieve this perfectly.
	* We can't use hashCode() here, need to implement a getHash function.
	*
	* In my opinion, the return result should be ArrayList<ArrayList<String>> which is more accurate.
	*
	* Second way: use Arrays.sort(charArray) and get a sorted char[], use it as key. Don't need getHash.
	*
	* Two String are Anagram feature:
	* 1. After sorting charArray, they are same.
	* 2. Every char frequency is same.
	*
	* Reference: http://blog.csdn.net/linhuanmars/article/details/21664747
	*
	* @author jeffwan
	* @date Apr 4, 2014
	*/
	public class Anagrams {
	public ArrayList<String> anagrams(String[] strs) {
	ArrayList<String> result = new ArrayList<String>();
	HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
	if (strs == null || strs.length == 0) {
	return result;
	}
	for (String str : strs) {
	char[] charArray = str.toCharArray();
	Arrays.sort(charArray);
	String key = new String(charArray);
	if (!map.containsKey(key)) {
	map.put(key, new ArrayList<String>());
	}
	map.get(key).add(str);
	}
	for (ArrayList<String> temp : map.values()) {
	if (temp.size() > 1) {
	result.addAll(temp);
	}
	}
	return result;
	}
	public ArrayList<String> anagrams2(String[] strs) {
	ArrayList<String> result = new ArrayList<String>();
	HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
	if (strs == null || strs.length == 0) {
	return result;
	}
	for (String str : strs) {
	int[] count = new int[26];
	for (int i = 0; i < str.length(); i++) {
	count[str.charAt(i) - 'a']++;
	}
	int hash = getHash(count);
	if (!map.containsKey(hash)) {
	map.put(hash, new ArrayList<String>());
	}
	map.get(hash).add(str);
	}
	for (ArrayList<String> temp : map.values()) {
	if (temp.size() > 1) {
	result.addAll(temp);
	}
	}
	return result;
	}
	public int getHash(int[] count) {
	int hash = 0;
	int a = 378551;
	int b = 63689;
	for (int num : count) {
	hash = hash * a + num;
	a = a * b;
	}
	return hash;
	}
	}

view raw Anagrams.java hosted with ❤ by GitHub