2.字母异位词分组

49. 字母异位词分组

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

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

示例 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. 自定义一个ArrayKey类型，专门用于判断是否是字母异位词，原理是，在ArrayKey中维护一个长度位26的数组，每一位存放一个字母出现的个数，在有参构造中，拿到字符串后，遍历每个字符，将对应的索引处的元素加一，重写ArrayKey的equals和hashCode方法，即可实现通过数组比较是否是字母异位词（如果是字母异位词，那么肯定有相同的数组，因为每个字符出现的次数都一样）
2. 第二种方法是基于排序的，既然字母异位词只是字符排列不相同的单词，那么我们可以将每个单词都进行一个排序，这样，如果是字母异位词，那么排序后的字符串一定都相等，实现上就是先将字符串转换为字符数组，然后使用Arrays.sort方法对字符数组进行排序后，再转回字符串，如果排序后的字符串相同，肯定是字母异位词

判断字母是不是异位词的问题解决后，我们就可以通过异位词判断之前是否添加过该异位词对于的列表，如果没有，则创建新的列表放入map中，如果有，则取旧的列表，直接将当前字符串添加到列表中即可

map的key表示可以判断是否是字母异位词的结构，方法一是一个ArrayKey对象，方法二则是排序后的字符串

map的value则是当前类型的字母异位词对应的存放原字符串的列表

题解代码

public class _2_groupAnagrams {
    /**
     * 通过一个数组判定字母异位词
     */
    static class ArrayKey {
        int[] array = new int[26];

        @Override
        public boolean equals(Object object) {
            if (this == object) return true;
            if (object == null || getClass() != object.getClass()) return false;
            ArrayKey arrayKey = (ArrayKey) object;
            return Objects.deepEquals(array, arrayKey.array);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(array);
        }

        public ArrayKey(String str) {
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                array[c - 97]++;
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<ArrayKey, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 字母异位词的ArrayKey一定相同
            ArrayKey key = new ArrayKey(str);
            List<String> list = map.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(str);
        }
        return new ArrayList<>(map.values());
    }
}

/**
 * 所有的字母异位词排序后都一样
 * @param strs
 * @return
 */
public List<List<String>> groupAnagrams(String[] strs) {
    // 「key:排序后的字母异位词，value:所有的字母异位词」
    HashMap<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        // 转字符数组
        char[] charArray = str.toCharArray();
        // 排序
        Arrays.sort(charArray);
        // 转字符串
        String string = Arrays.toString(charArray);
        // 存在则返回链表，不存在则创建新的链表
        List<String> list = map.computeIfAbsent(string, k -> new ArrayList<>());
        list.add(str);
    }
    return new ArrayList<>(map.values());
}