Group Anagrams 49 （LeetCode）

Question

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: All inputs will be in lower-case.

Solution

这道题看所给的字符串数组里面有多少个是同一个变形词变的。这道题同样使用HashMap来帮助存老值和新值，以及帮忙判断是否是变形词。

首先对每个string转换成char array然后排下序，HashMap里面的key存sort后的词，value存原始的词。然后如果这个排好序的词没在HashMap中出现过，那么就把这个sorted word和unsortedword put进HashMap里面。如果一个sorted word是在HashMap里面存在过的，则直接加入HashMap中对应的位置。最后将HashMap中的每一个value都加入result中即可。

代码如下：

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        if(strs == null || strs.length == 0){
            return res;
        }

        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for(int i = 0; i < strs.length; i++){
            String curt = strs[i];
            char[] curtArray = curt.toCharArray();
            Arrays.sort(curtArray);
            String sorted = new String(curtArray);
            if(!map.containsKey(sorted)){
                map.put(sorted, new ArrayList<String>());
            }
            map.get(sorted).add(curt);
        }

        for(String key : map.keySet()){
            res.add(map.get(key));
        }

        return res;
    }
}