面试算法33：变位词组

题目

给定一组单词，请将它们按照变位词分组。例如，输入一组单词[“eat”，“tea”，“tan”，“ate”，“nat”，“bat”]，这组单词可以分成3组，分别是[“eat”，“tea”，“ate”]、[“tan”，“nat”]和[“bat”]。假设单词中只包含英文小写字母。

分析

第一种方法是把每个英文小写字母映射到一个质数，如把字母’a’映射到数字2，字母’b’映射到数字3，以此类推，字母’z’映射到第26个质数101。每给出一个单词，就把单词中的所有字母对应的数字相乘，于是每个单词都可以算出一个数字。

例如，单词"eat"可以映射到数字1562（11×2×71）。如果两个单词互为变位词，那么它们中每个字母出现的次数都对应相同，由于乘法满足交换律，因此上述算法把一组变位词映射到同一个数值。例如，单词"eat"、"tea"和"ate"都会映射到数字1562。由于每个字母都是映射到一个质数，因此不互为变位词的两个单词一定会映射到不同的数字。

解

public class Test {
    public static void main(String[] args) {
        String[] strs = {"eat","tea","tan","ate","nat","bat"};
        List<List<String>> result= groupAnagrams(strs);
        for (List<String> res : result){
            System.out.println(res);
        }
    }

    public static List<List<String>> groupAnagrams(String[] strs){
        int[] hash = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

        Map<Long,List<String>> groups = new HashMap<>();
        for (String str : strs){
            long wordHash =1;
            for (int i = 0; i < str.length(); i++) {
                wordHash *= hash[str.charAt(i) - 'a'];
            }

            groups.putIfAbsent(wordHash,new LinkedList<>());
            groups.get(wordHash).add(str);
        }

        return new LinkedList<>(groups.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
25
26

分析

第二种方法是把一组变位词映射到同一个单词。由于互为变位词的单词的字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。

例如，把"eat"、“tea"和"ate"的字母按照字母表顺序排序都得到字符串"aet”。因此，可以定义一个哈希表，哈希表的键是把单词字母排序得到的字符串，而值为一组变位词。

解

public class Test {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> result = groupAnagrams(strs);
        for (List<String> res : result) {
            System.out.println(res);
        }
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sorted = new String(charArray);

            groups.putIfAbsent(sorted, new LinkedList<>());
            groups.get(sorted).add(str);
        }

        return new LinkedList<>(groups.values());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23