Group Anagrams

出处

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

Solution

这并不是一个完全排序的问题,而只要求分类,并且类别一定是有限个,选择用桶排序,类别数量等于桶的数量。对一般的桶排序,每一个不同的值就对应一个桶,而这里则是所有相同字母异序词(anagram)对应一个桶,因此需要找到一个哈希函数,要求是所有相同字母异序词的哈希值相同,对应同一个桶。一种做法是将字符串排序后的结果作为字符串的哈希值。

Complexity

假定字符串平均长度为k,数量为n,那么平均复杂度为O(klogk*n)。

Code

// Use the modification of the bucket sort
public void sort(String[] array){
    HashMapList<String, String> mapList = new HashMapList<String, String>();

    for (String s : array){
        String key = sortChars(s);
        mapList.put(key, s);
    }

    int index = 0;
    for (String key : mapList.keySet()){
        ArrayList<String> list = mapList.get(key);
        for (String t : list){
            array[index] = t;
            index++;
        }
    }

    String sortChars(String s){
        char[] content = sortChars.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }
}