[leetcode] 49. 字母异位词分组

admin2024-04-03  0

文章目录

  • 题目描述
  • 解题方法
    • 排序
      • java代码
      • 复杂度分析

题目描述

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示:

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

解题方法

排序

只要搞懂什么是字母异位词,思路还是挺简单的。

我们可以用哈希表存储字母异位词key就用字母异位词从小到大排序后组成的单词,value存储相同单词的字母异位词

举个例子,假设字符串数组为["eat", "tea", "tan", "ate", "nat", "bat"],那按照上面的思路,我们的哈希表就为如下所示。

keyvalue
aet[eat, tea, ate]
ant[tan, nat]
abt[bat]

java代码

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for(String valueStr : strs) {
        char[] cs = valueStr.toCharArray();
        Arrays.sort(cs);
        String keyStr = new String(cs);
        if (!map.containsKey(keyStr)) {
            map.put(keyStr, new ArrayList<>());
        }
        map.get(keyStr).add(valueStr);
    }
    List<List<String>> result = new ArrayList<>(map.values());
    return result;
}

复杂度分析

时间复杂度: O ( n k l o g k ) O(nklogk) O(nklogk) n n n为字符串数组长度, k k k为数组中最长字符串的长度。需要遍历一次字符串数组;对于每个字符串,需要 O ( k l o g k ) O(klogk) O(klogk)的时间复杂度进行排序。
空间复杂度: O ( n k ) O(nk) O(nk),需要提供哈希表存储所有字符串。


  • 个人公众号
    [leetcode] 49. 字母异位词分组,个人公众号,第1张
  • 个人小游戏
    [leetcode] 49. 字母异位词分组,个人小游戏,第2张
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!