leetcode: 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:

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

原问题链接：https://leetcode.com/problems/anagrams/

 

问题分析

　　这个问题其实相对来说比较简单，因为它本身的要求是将一些包含相同字符的词组合在一起，并且是排序的。这里的难点在于第一步，怎么将这些包含有相同个数字符的词放在一起。因为它们由相同的字符集合构成，仅仅是因为排列的顺序不一样。

　　其实这一类anagram的问题有一个固定的解决套路，虽然它们这些字符集构成的词有千变万化，但是既然是相同的词，我们将一个词里所有的字符首先排序得到一个字符串数组对于所有anagram来说就是一样的。所以我们可以将一个词里所有字符构成的串排序，然后将这个结果作为key，所有相同结果的词都放到同一个key下面。这样我们就可以很自然的想到用一个Map来解决问题。

　　在详细的实现时，我们可以声明一个HashMap<String, List<String>>，key是根据一个字符串排序后得到的一个串，value是相同的anagram构成的列表。因为要求后面的结果是排序的，我们在后面将所有的value值都从Map里取出来的时候，先对value排一下序再加入到最终的列表中即得到最终的结果。详细实现如下：

 

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for(String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if(!map.containsKey(key)) map.put(key, new ArrayList<>());
            map.get(key).add(s);
        }
        for(String key : map.keySet()) {
            List<String> list = map.get(key);
            Collections.sort(list);
            result.add(list);
        }
        return result;
    }
}