Leetcode 每日一题 49.字母异位词分组

问题描述

示例

示例 1

示例 2

示例 3

约束条件

解决方案

思路

算法步骤

过题图片

代码实现

复杂度分析

题目链接

结论

问题描述

给定一个字符串数组，需要将其中的字母异位词分组。字母异位词是指通过重新排列源单词的所有字母得到的新单词。要求可以按任意顺序返回结果列表。

示例

示例 1

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

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

示例 2

输入: strs = [""]

输出: [[""]]

示例 3

输入: strs = ["a"]

输出: [["a"]]

约束条件

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

解决方案

思路

解决这个问题的关键在于识别哪些字符串是字母异位词。由于字母异位词的字母种类和数量完全相同，我们可以通过对字符串中的字母进行排序，然后比较排序后的字符串是否相同来判断两个字符串是否为字母异位词。

算法步骤

创建一个空的Map，用于存储排序后的字符串和对应的原始字符串列表。
遍历输入的字符串数组strs。
对于每个字符串，将其转换为字符数组，并进行排序。
将排序后的字符数组转换回字符串。
检查Map中是否已经存在这个排序后的字符串作为键，如果存在，则将原始字符串添加到对应的列表中；如果不存在，则创建一个新的列表，并将原始字符串添加进去。
将这个列表与排序后的字符串作为键一起存入Map。
最后，将Map中的所有值（即所有分组好的列表）放入一个新的列表中，并返回。

过题图片

代码实现

java

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String sortedStr = new String(array); // 获取排序后的字符串
            List<String> tempList = map.getOrDefault(sortedStr, new ArrayList<>());
            tempList.add(str); // 将排序后相等的字符串存入一个集合
            map.put(sortedStr, tempList); // 将该字符串存入以 “sortedStr”为key，list为value的map键值对中
        }
        return new ArrayList<>(map.values()); // 返回所有分组好的列表
    }
}