49 Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order. All inputs will be in lower-case.

Analysis

1.How do we know whether a string is a anagram to a other word?

Sol 1: convert String to char[], compare each ele in char, if all match, they are.

2.How to group them?

Sol1 : using HashMap, Key is a String , Value is a ArrayList.

3.How to define Key?

def 1: convert String to char[], sort it and build a String according this sorted char[]

Solution

public List<List<String>> groupAnagrams(String[] strs) {

        //sort strs as lexicographic order ----->O(NlgN)
        Arrays.sort(strs);

        //initialize
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, ArrayList<String>> anagramsGroup= new HashMap<String, ArrayList<String>>();

        //traverse input array strs ----->O(N)
        for(String s : strs) {

            //group a string with its anagrams
            String Key = generateKey(s);
            if(anagramsGroup.containsKey(Key)) {
                anagramsGroup.get(Key).add(s);
            }
            else {
                ArrayList<String> temp = new ArrayList<String>();
                temp.add(s);
                anagramsGroup.put(Key, temp);
            }
        }

        //generate result ----->O(N)
        Set<String> set = anagramsGroup.keySet();
        Iterator<String> iter = set.iterator();
        while(iter.hasNext()) {
            String hashKey = iter.next();
            res.add(anagramsGroup.get(hashKey));
        }

        return res;
    }

    private String generateKey(String s) {
        String key = "";

        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);

        for(int i=0; i<charArray.length; i++) {
            key += charArray[i];
        }

        return key;
    }

Solution: 利用几个方法来简化一些操作

//String Constructor
//利用char[] 直接构建String
String(char[] value)

//Map method
//返回包含map的各value的collection：Returns a Collection view of the values contained in this map.
Collection<V>    values()

//Arraylist method
//利用已有collection，直接构建Arraylist
boolean    addAll(Collection<? extends E> c)