合并两个有序链表 | LeetCode 21

题目描述

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

​

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

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

​

题目解析

字母异位词的字母成分一定是相同的，目标是把相同字母成分的字符串放到一个分组里。

​

属于根据特征进行归类的模式，应该利用散列表。

因此分两步，

1. 初始化一个哈希表，key为字母成分(通过排序后的字母串作为唯一标识)，值为该成分下的所有字母异位词字符串；
2. 遍历元素字符串，如果该字母成分未出现在哈希表中，加入哈希表，字母成分串对应的组合也增加该元素；如果已出现在哈希表，获取组合列表，追加该元素

​

参考代码

以下为 Java 代码。

​

​

复杂度分析

​

• 时间复杂度：O(nklog⁡k)。

• 其中 n 是入参数组 strs 中的字符串的数量，k 是字符串的最大长度。
• 需要遍历 n 个字符串，对于每个字符串，需要 O(klog⁡k)的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklog⁡k)。

• 空间复杂度：O(nk)。

• 其中 n 是入参数组 strs 中的字符串的数量，k 是字符串的的最大长度。需要用哈希表存储全部字符串。