49. 字母异位词分组

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 

示例 1：

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

说明

所有输入均为小写字母。
不考虑答案输出的顺序。

 

题目分析

　　从字母异位词上找他们的共同点，字母相同，且字母出现的次数也相同。

排序法

　　可以发现将每个字符串里字母排序后，字母异位词是相同的，可以考虑哈希表，key为排好序的字符串。

　　时间复杂度度：o(n)*o(klogk)

  ArrayList以数组的方式存储数据，里面的元素是有顺序，可以重复的；而HashMap将数据以键值对的方式存储，键的哈希码（hashCode）不可以相同，相同后面的值会将前面的值覆盖，值可以重复，里面的元素无序。

 1 class Solution {
 2     public List<List<String>> groupAnagrams(String[] strs) {
 3         //排序法
 4         HashMap<String,ArrayList> res = new HashMap<>();
 5         for(String s:strs){//o(n)
 6             //排序
 7             char[] temp = s.toCharArray();//toCharArray()将字符串对象中的字符转换为一个字符数组。
 8             Arrays.sort(temp);//Arrays类的静态方法，对一个数组的所有元素进行排序，并且是按从小到大的顺序//o(nlogn)
 9             String key = new String(temp);
10             //不存在key就添加一个
11             if(!res.containsKey(key)){
12                 res.put(key,new ArrayList<>());
13             }
14             res.get(key).add(s);//将当前的字符串存入当前的key里
15          }
16          return new ArrayList(res.values());
17     }
18 }

 

哈希法

　　优于排序法

　　把每个字符串从a-z排序后，每个字符出现的次数相同为字母异位词。出现的次数放到一个数组里，数组不能被哈希，需要一个String被哈希。

　　所有的值前面加一个#。#1#0#0#12#0#1

　　

 1 class Solution {
 2     public List<List<String>> groupAnagrams(String[] strs) {
 3         //哈希表
 4         HashMap<String,ArrayList<String>> map = new HashMap<>();  
 5  
 6         for(String s:strs){
 7             int count[] = new int[26]; 
 8             for(char c:s.toCharArray()){
 9                 count[c-'a']++;
10             }
11             //数组不能被哈希
12             StringBuilder sb = new StringBuilder();
13             for(int cou : count){
14                 sb.append("#");
15                 sb.append(cou);
16             }
17             String key = sb.toString();
18              System.out.println("key:"+key);
19             if(!map.containsKey(key)){
20                 map.put(key,new ArrayList<>());
21             }
22             map.get(key).add(s);
23         }   
24         return new ArrayList(map.values());                             
25     }
26 }