String - 49. Group Anagrams

49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

思路：

问题主要是如何选出字符串数组中同构异形的字符串，所以制造一个唯一标识，或者对每一个字符串进行排序，加上O(1)操作的map来找出相同的字符串。

代码：

java：

class Solution {

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if (strs == null || strs.length == 0) return res;
        
        Map<String,Integer> map = new HashMap<>();        
        for (String str : strs) {
            // 1. count sort
            char[] arr = new char[26];
            for(int i = 0; i < str.length(); i++){
                arr[str.charAt(i) - 'a']++;
            }
            String key = String.valueOf(arr);

            // 2. add res
            if(map.containsKey(key)) {
                List<String> exsitList= res.get(map.get(key));
                exsitList.add(str);
            } else {
                List<String> temp = new ArrayList<>();
                temp.add(str);
                map.put(key, res.size()); // res.size() as res index;
                res.add(temp);
            }
        }
        
        return res;
    }
}