leetcode49.字母异位词分组

一、题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，“eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

二、题目解析

1、全部异位词共性：排序后唯一，可以此作为map的key，此key下的全部异位词组成list

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs == null || strs.length == 0){
            return null;
        }
        HashMap<String,List<String>> map = new HashMap<>();
        for(int i = 0;i < strs.length;i++){
            String curKey = sortString(strs[i]);
            if(!map.containsKey(curKey)){
                List<String> curList = new ArrayList<>();
                curList.add(strs[i]);
                map.put(curKey,curList);
            }else{
                List<String> curList = map.get(curKey);
                curList.add(strs[i]);
                map.put(curKey,curList);
            }
        }
        List<List<String>> res = new ArrayList<>();
        for(Map.Entry<String,List<String>> entry : map.entrySet()){
            List<String> cur = entry.getValue();
            res.add(cur);
        }
        return res;
    }
    public String sortString(String s){
        char[] chs = s.toCharArray();
        Arrays.sort(chs);
        return new String(chs);
    }
}

运行：

2、在1的基础上优化

• map.getOrDefault可代替if-else结构，简化代码
• map.values()可把map的全部值快速提取转换成list
  • new ArrayList<>(sourceMap.values())
  • new HashSet<>(sourceMap.values());
• String.valueOf()可支持将基本数据类型，char数组，object对象转换成字符串
  简化代码如下：

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