Leetcode: Group Anagrams
发布日期:2025-04-05 03:39:31 浏览次数:9 分类:精选文章

本文共 2000 字,大约阅读时间需要 6 分钟。

举个例子,假设输入是["abc","cba","azyg","cba","cc","acb"],那么处理步骤是这样的:

  • 将每个单词排序:

    • "abc" 排序后变为 "abc"
    • "cba" 排序后变为 "abc"
    • "azyg" 排序后变为 "abyz"
    • "cba" 排序后变为 "abc"
    • "cc" 排序后变为 "cc"
    • "acb" 排序后变为 "acb"
  • 创建哈希表并将排序后的字符串作为键,将原始单词作为值存入对应的列表:

    • "abc" 对应的列表包含["abc", "cba", "cba"]
    • "abyz" 对应的列表包含["azyg"]
    • "cc" 对应的列表包含["cc"]
    • "acb" 对应的列表包含["acb"]
  • 最后,对每个列表进行排序:

    • "abc" 列表按字典序排列是 ["abc", "cba", "cba"](实际上因为重复的单词,会影响列表的排序,但这里示例中没有重复单词,只是为了描述)
    • "abyz" 列表只有一个元素
    • "cc" 列表只有一个元素
    • "acb" 列表只有一个元素
  • 最终返回所有包含多个单词的列表,用字典序排列:

  • [["abc", "cba", "cba"], ["abyz"], ["cc"], ["acb"]]

    这就是完成任务的基本步骤,下面我将详细解析如何实现这个功能。整个代码思路是基于将每个单词排序后作为键,然后找到相同的键对应的所有单词,最后按照字典序返回这些单词列表。

    代码解析

    public class Solution {    public List
    > groupAnagrams(String[] strs) { List
    > res = new ArrayList<>(); Map
    > map = new HashMap<>(); for (String item : strs) { char[] array = item.toCharArray(); Arrays.sort(array); String aftersort = new String(array); if (map.containsKey(aftersort)) { List
    list = map.get(aftersort); list.add(item); } else { List
    newlist = new ArrayList<>(); newlist.add(item); map.put(aftersort, newlist); } } for (List
    each : map.values()) { if (each.size() > 1) { Collections.sort(each); res.add(new ArrayList<>(each)); } } return res; }}

    关键步骤解释:

  • 初始化变量

    • 使用List<List<String>> res 来保存最终的结果,每一组的单词按字典序排列。
    • 使用Map<String, List<String>> map 来存储相同排序后字符串对应的单词列表,键是排序后的字符串,值是List<String>
  • 遍历输入字符串数组:对于每个输入的字符串item,执行以下操作:

    • item转换为字符数组char[] array
    • 对字符数组进行排序。
    • 将排序后的字符数组转换为字符串aftersort,作为关键。
    • 检查map中是否存在aftersort这个键,如果存在,将item添加到对应的列表中;如果不存在,创建一个新的列表,将item添加进去,并将这个列表放在map中。
  • 收集结果并排序

    • 遍历map中的每个值(即每个单词列表)。
    • 如果列表中有超过一个元素,说明这些单词是变位词。
    • 对该列表进行排序,以确保结果是按字典序排列的。
    • 将排序后的列表加入到res中。
  • 返回结果:返回res,其中包含所有变位词分组后的结果,每一组都是按字典序排列。

  • 注意事项:

    • 处理空字符串:在排序和哈希表操作中,确保对空字符串正确处理。可以通过Arrays.sort()直接排序空字符数组,得到空字符串。
    • 排序稳定性:字符串排序是稳定的,如果多个单词是完全相同的,会被正确归类到同一组中。
    • 性能考虑:对于非常大的输入数组或长字符串,可能需要考虑优化排序方法或使用更高效的数据结构。

    通过以上方法,可以高效地将给定的字符串数组按照变位词分组,并按字典序排列每一组中的单词,满足题目的要求。

    上一篇:Leetcode: Remove Duplicates from Sorted Array II
    下一篇:Leetcode963. Minimum Area Rectangle II最小面积矩形2

    发表评论

    最新留言

    感谢大佬
    [***.8.128.20]2025年04月18日 18时13分26秒

    关于作者

        喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
    -- 愿君每日到此一游!

    推荐文章