题目地址(49. 字母异位词分组)

https://leetcode-cn.com/problems/group-anagrams/

题目描述

  1. 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
  3. 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
  7. 示例 1:
  9. 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
  10. 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
  12. 示例 2:
  14. 输入: strs = [""]
  15. 输出: [[""]]
  18. 示例 3:
  20. 输入: strs = ["a"]
  21. 输出: [["a"]]
  25. 提示：
  27. 1 <= strs.length <= 104
  28. 0 <= strs[i].length <= 100
  29. strs[i] 仅包含小写字母

前置知识


公司

  • 暂无

思路

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.         public List<List<String>> groupAnagrams(String[] strs) {
  4.             HashMap<String, List<String>> map = new HashMap<>();
  5.             for (String str : strs) {
  6.                 char[] chars = str.toCharArray();
  7.                 //将字符串变成数组并排序
  8.                 Arrays.sort(chars);
  9.                 //不同顺序的字符经过排序得到相同的key
  10.                 String key = new String(chars);
  11.                 //mapgetkey 如果有值就返回结果 不然就返回新列表
  12.                 List<String> orDefault = map.getOrDefault(key, new ArrayList<String>());
  13.                 //列表添加当前str并添加到map中
  14.                 orDefault.add(str);
  15.                 map.put(key, orDefault);
  16.             }
  17.             return new ArrayList<List<String>>(map.values());
  18.         }
  19.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：49. 字母异位词分组 - 图1#card=math&code=O%28nklogk%29&id=ZLuHl)
  • 空间复杂度：49. 字母异位词分组 - 图2#card=math&code=O%28n%29&id=lDZgj)