网站建设 项目经验,免费网站模板psd,家在深圳 业主论坛,商洛市住户和城乡建设局网站信息价题目
给定一组单词#xff0c;请将它们按照变位词分组。例如#xff0c;输入一组单词[“eat”#xff0c;“tea”#xff0c;“tan”#xff0c;“ate”#xff0c;“nat”#xff0c;“bat”]#xff0c;这组单词可以分成3组#xff0c;分别是[“eat”#xff0c;“…题目
给定一组单词请将它们按照变位词分组。例如输入一组单词[“eat”“tea”“tan”“ate”“nat”“bat”]这组单词可以分成3组分别是[“eat”“tea”“ate”]、[“tan”“nat”]和[“bat”]。假设单词中只包含英文小写字母。
分析
第一种方法是把每个英文小写字母映射到一个质数如把字母’a’映射到数字2字母’b’映射到数字3以此类推字母’z’映射到第26个质数101。每给出一个单词就把单词中的所有字母对应的数字相乘于是每个单词都可以算出一个数字。
例如单词eat可以映射到数字156211×2×71。如果两个单词互为变位词那么它们中每个字母出现的次数都对应相同由于乘法满足交换律因此上述算法把一组变位词映射到同一个数值。例如单词eat、tea和ate都会映射到数字1562。由于每个字母都是映射到一个质数因此不互为变位词的两个单词一定会映射到不同的数字。
解
public class Test {public static void main(String[] args) {String[] strs {eat,tea,tan,ate,nat,bat};ListListString result groupAnagrams(strs);for (ListString res : result){System.out.println(res);}}public static ListListString 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};MapLong,ListString 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};ListListString result groupAnagrams(strs);for (ListString res : result) {System.out.println(res);}}public static ListListString groupAnagrams(String[] strs) {MapString, ListString 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());}
}
