题目

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

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

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

问题分析

题目中可以看出，我们要找出满足某一种条件的字符串集合，这个条件是：字母全对，只是错位
针对这种情况，我们可以利用算法，先将字符串排序，再比较(排序之后的两个错位字符串会变成一样的)。
或者统计每个字符串所出现字母次数，放入哈希表进行比较。

方法一：排序数组分类

  1. 思路

当且仅当它们的排序字符串相等时，两个字符串是字母异位词。

  1. 算法

维护一个映射 ans : {String -> List}，其中每个键 $K$ 是一个排序字符串，每个值是初始输入的字符串列表，排序后等于 $K$。

在 Java 中，我们将键存储为字符串，例如，code。

方法二：计数分类

1.思路

当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。

  1. 算法

我们可以将每个字符串 $\text{s}$ 转换为字符数 $\text{count}$，由26个非负整数组成，表示 $ \text{a} $，$\text{b}$，$\text{c}​$ 的数量等。我们使用这些计数作为哈希映射的基础。

在 Java 中，我们的字符数 count 的散列化表示将是一个用 ＃ 字符分隔的字符串。 例如，abbccc 将表示为 ＃1＃2＃3＃0＃0＃0 …＃0（表示 a 出现了1次， b 出现了2次），其中总共有26个条目。。

代码-排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            //将每个字符串转换成字符数组
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

代码-计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            //初始化字母表
            Arrays.fill(count, 0);
            //统计一个字符串中字幕出现情况
            for (char c : s.toCharArray()) count[c - 'a']++;
            //将统计的情况转换成StringBuilder key = 统计情况 value = 同一个错位词Group
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            //如果key相同，说明统计情况一样，便为错位词Group，添加到List
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

哈希表相关操作

哈希表实现原理

关于hash的具体实现规则，Java源代码请看之前Java基础集合篇。

Hash家族

  1. Hashtable 是一个包含单向链表的二维数组，其数据结构的数组中是 Entry<K,V> 存储， entry 对象。 Hashtable 有洁癖，不允许存入其中的 key 或者 value 为 null。Hashtable 是线程安全的，所有的方法均用 synchronized 修饰，这样在任一时刻，只有一个线程可以写 Hashtable，因此，对于频繁写操作的业务逻辑，速度会非常慢。

  2. HashMap 是最常用的 Map 型数据结构，它根据键的 hashCode() 值存储数据。HashMap 允许一个 key 为 null ,允许多个 value 为空，HashMap 不支持线程的同步，即可能会出现在同一时刻有多个线程同时写 HashMap ,会产生数据的不一致。如果在修改代码的过程中，需要给 HashMap 限制为线程同步的，可以采用 Collections.synchronizedMap(map); 方法使得HashMap 可以同步。

  3. ConcurrentHashMap是基于这样的考虑：降低锁的粒度。在 Hashtable 中的关键字是使用 synchronized 基于整张表结构的，锁的粒度太大，它每次通过锁住整张表让线程独占，来保证安全性。

  4. LinkedHashMap 保存了记录的插入顺序，在使用 Iterator 遍历 LinkedHashMap 的时候，先得到的记录肯定是先插入的。在遍历的时候会比 HashMap 慢，因为 HashMap 是以O(1)来设计存取的。并且 LinkedHashMap 继承自 HashMap ，拥有它的全部特性。

  5. TreeMap是基于红黑树实现的，它是一种有序的存储结构，并且程序员可以自己定义排序器。TreeMap 默认会按存入的键值 key 来排序，默认是按升序排序，当然也可以指定排序的比较器。 TreeMap 同样有洁癖，不允许存入 null 值。使用 Iterator 遍历出来的 TreeMap 往往是有序的。

总结：常用HashMap，允许null插入；有两个子类：ConcurrentHashMap和LinkedHashMap。前者用来弥补线程安全，后者用来弥补有序。此外还有Hashtable和TreeMap。虽然CouncurrentHashMap性能明显优于Hashtable，但是并不能完全取代Hashtable，因为遍历ConcurrentHashMap的迭代器是弱一致的。TreeMap数据结构则可以帮助我们得到一个有序的结果，适用于需要输出排序结果的场景。

注意：Java 8 改进特性

Java 8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。在 Java 8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

几个常用hash函数

一般做题的时候，通常是用 HashMap 解决问题。

  1. 创建一个hashMap
1
Map<String, List> ans = new HashMap<String, List>();

在尖括号里，第一个类型是 KEY , 第二个类型是 VALUE 。

  1. 判断元素是否存在
1
2
boolean              containsKey(Object key)
boolean              containsValue(Object value)
  1. 根据 key 找 value
1
V                    get(Object key)
  1. 添加一对新的键值组合
1
V                    put(K key, V value)
  1. 删除对应的key
1
V                    remove(Object key)
  1. 其他函数
1
2
3
4
5
6
7
8
void                 clear()
Object               clone()
Set<Entry<K, V>>     entrySet()
boolean              isEmpty()
Set<K>               keySet()
void                 putAll(Map<? extends K, ? extends V> map)
int                  size()
Collection<V>        values()

hashmap应用场景

在实际应用中，hashMap数据结构 适用以下几个情况

  • 需要遍历许多次才能解决的问题，hashMap 可以大大减小算法的时间复杂度
  • 需要记忆性的问题，像这道题，我们需要记住每个字符的所属情况，并给他们打一个专属标记。

更多关于哈希表的问题

更多关于哈希表的问题请转到链表标签