本文主要是介绍面试算法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());}
}
这篇关于面试算法33:变位词组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!