图解LeetCode——49. 字母异位词分组

一、题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

二、示例

2.1> 示例 1:

【输入】 strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

【输出】 [["bat"],["nat","tan"],["ate","eat","tea"]]

2.2> 示例 2:

【输入】 strs = [""]

【输出】 [[""]]

2.3> 示例 3:

【输入】 strs = ["a"]

【输出】 [["a"]]

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

三、解题思路

根据题目描述，我们要将字母异位词组合在一起。其实本题的难点之一就是对于这个“字母异位词”的理解。我们以eat为例，它的字母异位词包括：eat、aet、ate、eta、tea、tae；所以，对于字母异位词来说，就是我们将e、a、t这3个字符进行随意组合即可。

那么，了解了字母异位词的含义了之后，我们再来看这道题的解题思路，这里我们主要需要解决两个问题：

【问题1】获得同组的字母异位词；

【问题2】将不同的字母异位词组合在一起；

关于第一个问题的解决办法，我们可以通过对一个字符串的所有字符进行排序，即通过char[] sc = str.toCharArray()和Arrays.sort(sc)获得有序的sc，以上面的“eat”为例，所有的6个字母异位词排序后都为“aet”。我们创建Map数据结构的变量，以“aet”作为key，以List存储原始字符串为value，存储到Map结构中。这样，当我们遍历完整个strs字符串数组之后，就完成了对每个字符串元素进行的分组操作了。

以上就是本题的具体解题思路，下面我们还是按照惯例，以输入strs = ["eat", "tea", "tan", "ate", "nat", "bat"]为例，看一下具体的操作流程。请见下图所示：

四、代码实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap();
        for (String str : strs) {
            char[] sc = str.toCharArray();
            Arrays.sort(sc);
            String key = new String(sc);
            if (map.get(key) == null) {
                List list = new ArrayList();
                list.add(str);
                map.put(key, list);
            } else map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」