leetcode
leetcode 1 ~ 50
字母异位词分组

字母异位词分组

难度:

标签:

题目描述

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

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

 

示例 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] 仅包含小写字母

代码结果

运行时间: 68 ms, 内存: 19.8 MB


/* 
 * 思路:
 * 使用Java Streams流式处理,通过对每个字符串进行排序,
 * 然后将其收集到Map中,键为排序后的字符串,值为相应的字符串列表。 
 */
 
import java.util.*;
import java.util.stream.Collectors;
 
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(s -> {
                char[] charArray = s.toCharArray();
                Arrays.sort(charArray);
                return new String(charArray);
            })).values());
    }
}

解释

方法:

该题解的思路是利用哈希表来将字母异位词分组。具体做法是:遍历字符串数组中的每个字符串,对于每个字符串,统计其中每个字母出现的次数,并将统计结果转换为一个长度为26的元组作为哈希表的键,字符串作为对应键的值。这样,所有字母异位词都会被映射到哈希表中的同一个键上,最后将哈希表中的所有值(即分组后的字母异位词列表)转换为列表返回即可。

时间复杂度:

O(n * k)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择使用长度为26的列表来表示每个字符串的字符出现次数,而不是使用哈希表或其他数据结构?
使用长度为26的列表来表示每个字符串的字符出现次数是因为这种方法在空间和时间效率上都很高。由于英文字母只有26个,一个固定大小的数组足以容纳所有可能的字母,并且访问数组元素的时间复杂度是O(1)。相比之下,哈希表虽然灵活但在处理小型固定范围的数据时,其额外的哈希计算和潜在的冲突解决机制可能会导致不必要的开销。数组通过直接使用字母的索引来避免这些问题,因此在处理固定范围数据时更为高效。
🦆
将字符出现次数的列表转换为元组用作哈希键的理由是什么?是否有其他数据结构可以用作哈希键?
将字符出现次数的列表转换为元组用作哈希键的主要原因是元组在Python中是不可变的,因此可以用作哈希表的键。不可变性是必要的,因为哈希表的键必须是不变的以确保哈希表的正确性和稳定性。列表由于是可变的,不能直接用作哈希键。尽管如此,理论上可以使用其他不可变或固定值的数据结构作为哈希键,例如字符串或冻结集合(frozenset),但在这种情况下,由于性能和简便性,元组是最合适的选择。
🦆
在哈希表中,如果两个字符串是字母异位词但顺序不同,它们如何确保映射到同一个键上?
在哈希表中,两个字符串如果是字母异位词,即使它们的字符顺序不同,它们也会映射到同一个键上,因为它们的字符出现次数是相同的。算法通过统计每个字符串中每个字母的出现次数,并将这些次数存储在一个固定长度的列表(或数组)中,确保了这一点。将这些列表转换为元组后,这些元组将作为哈希键。由于字母异位词具有相同的字符统计数据,因此它们的键(即元组)也将相同,从而确保它们被映射到同一个哈希表条目上。
🦆
对于空字符串,该算法如何处理?它们在哈希表中的键是什么样的?
对于空字符串,该算法同样会创建一个长度为26的数组,其中所有元素的初始值都为0,因为空字符串不包含任何字符。因此,空字符串的字符出现次数列表是全零的列表。将这个列表转换为元组后,得到的元组也将全为零。在哈希表中,所有空字符串都将共享相同的键(即全零的元组),并被分组在一起。这意味着算法能够有效地处理空字符串,将它们归为一组,而不会导致错误或异常。

相关问题

有效的字母异位词

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 st 中每个字符出现的次数都相同,则称 st 互为字母异位词。

 

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

 

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • st 仅包含小写字母

 

进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

移位字符串分组

移位字符串分组