字母异位词分组
# 📃 题目描述
题目链接:
- 剑指 Offer II 033. 变位词组 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 49. 字母异位词分组 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
# 🔔 解题思路
上道题 剑指 Offer II 032. 有效的变位词 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 把相同的两个字符串不视为异位词,而本道题是把相同的两个字符串视为异位词的,小细节,注意下就行
思路:把一组变位词映射到同一个单词。
由于互为变位词的单词的字母出现的次数分别相同,因此如果把单词中的字母排序就会得到相同的字符串。例如,把"eat"、"tea"和"ate"的字母按照字母表顺序排序都得到字符串"aet"。
因此,可以定义一个哈希表,哈希表的 key 是把单词字母排序得到的字符串,而 value 为对应的一些变位词(通过排序后能够和 key 相同的字符串):
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// key: 排序好的字符串,value: 通过排序后能够和 key 相同的字符串
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] charArray = str.toCharArray();
// 按照字母顺序排序
Arrays.sort(charArray);
String sorted = new String(charArray);
map.putIfAbsent(sorted, new ArrayList<>());
map.get(sorted).add(str);
}
List<List<String>> res = new ArrayList<>();
for (String key : map.keySet()) {
res.add(map.get(key));
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:主要就是循环和排序的时间:如果每个单词平均有 m 个字母,排序一个单词需要 O(mlogm) 的时间。假设总共有n个单词,该算法总的时间复杂度是O(nmlogm)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10