leetcode49.字母异位词分组

题目链接

题解: hash

本题的思路为：使用hash，需要存储key以及value；对应Java中的HashMap。首先遍历字符串数组，对于每个字符串都先将其转换为字符数组，然后进行排序，再使用String.valueOf方法重组为新的字符串。
示例：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]

对每一个字符串转换字符数组并排序重组后只有三种：

"aet"
"ant"
"abt"

将以上三种字符串作为HashMap存储的key,使用一个List保存原字符串即可。

代码如下：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs == null || strs.length == 0){
            return new ArrayList<List<String>>();
        }
        HashMap<String,List<String>> map = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            char[] chs = strs[i].toCharArray();
            Arrays.sort(chs);
            String key = String.valueOf(chs);
            if(map.containsKey(key)){
                map.get(key).add(strs[i]);
            }else{
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                map.put(key,list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

本思路的时间复杂度分析：
排序的时间复杂度为O(klogk),其中k为字符串数组中最长的字符串长度。另外遍历一遍字符串数组的时间复杂度为O(n),所以该算法的时间复杂度为O(n × klogk)。
额外空间复杂度则是使用了char数组以及hashmap。额外空间复杂度为O(n × k)。
代码执行结果如下: