Leetcode算法Java全解答--49. 字母异位词分组

快来打我* 2022-04-06 03:43 149阅读 0赞

# Leetcode算法Java全解答–49. 字母异位词分组 #

### 文章目录 ###

*  Leetcode算法Java全解答--49. 字母异位词分组
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

说明：

所有输入均为小写字母。  
不考虑答案输出的顺序。

示例

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

## 想法 ##

用一个hashMap<String, List>来存储出现的单词

key是单词进行排序之后的数据（比如eat、tea、ate，这些的key都是aet）

value是数组

## 结果 ##

超过97%的测试案例

时间复杂度/空间复杂度：n/n

## 总结 ##

// TODO

## 代码 ##

### 我的答案 ###

public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return Collections.emptyList();
        }
        
        Map<String, List<String>> ans = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList<String>());
            }
            ans.get(key).add(str);
        }
        
        return new ArrayList(ans.values());
    }

### 大佬们的答案 ###

class Solution {
        public List<List<String>> better(String[] strs) {
            if (strs.length == 0) {
                return Collections.emptyList();
            }
            Map<String, List> ans = new HashMap<String, List>();
            int[] count = new int[26];
            for (String s : strs) {
                Arrays.fill(count, 0);
                for (char c : s.toCharArray()) {
                    count[c - 'a']++;
                }
    
                StringBuilder sb = new StringBuilder("");
                for (int i = 0; i < 26; i++) {
                    sb.append('#');
                    sb.append(count[i]);
                }
                String key = sb.toString();
                if (!ans.containsKey(key)) {
                    ans.put(key, new ArrayList());
                }
                ans.get(key).add(s);
            }
            return new ArrayList(ans.values());
        }
    }

### 测试用例 ###

@Test
    public void test049() {
        // 创建测试案例
        String[] arr1 = new String[] { "eat", "tea", "tan", "ate", "nat", "bat" };
    
        // 测试案例期望值
        List<List<String>> expResult1 = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        list1.add("ate");
        list1.add("eat");
        list1.add("tea");
        List<String> list2 = new ArrayList<>();
        list2.add("nat");
        list2.add("tan");
        List<String> list3 = new ArrayList<>();
        list3.add("bat");
        expResult1.add(list1);
        expResult1.add(list2);
        expResult1.add(list3);
    
        // 执行方法
        Solution049 solution049 = new Solution049();
        List<List<String>> result1 = solution049.groupAnagrams(arr1);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
    
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan