面试算法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());}
}

分析

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

例如，把"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());}
}