深圳做营销网站建设,辽宁短视频搜索seo哪家实惠,注册网站刀具与钢材范围,佛山建网站费用题目描述
给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“n…题目描述
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 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
题目看起来比较简单找出字符串数组中字母相同的字符串放在一个列表中最后把所有列表返回思路就是分两步第一步找出来第二步放在列表中 首先是怎么找出字母相同的数组简单思路就是把单词中的每个字母对应的ASCII值加起来这样做的问题也很明显会出现单词不一样但是加起来的值一样做了改进对字母的ASCII值做平方再相加目的是为了两个字母的差值更大减小单词不一样值加起来一样的概率但是这个不是正确解决思路只是一种投机行为这种方式只能减小但不能完全消除所以按照这个思路的代码通过了107 / 120个测试用例 第二步就是放在列表中依照上述思路就想到了mapkey是单词字母的ASCII值做平方再相加的结果value就是一个列表里面是结果相同的单词按照这种思路遍历完字符串数组再遍历map,将map的value添加到列表中返回以下是代码 public ListListString groupAnagrams(String[] strs) {ListListString res new ArrayList();if (strs.length 0) {return res;}if (strs.length 1) {res.add(new ArrayList(Collections.singleton(strs[0])));return res;}MapInteger, ListString listMap new HashMap();for (String s : strs) {int sum 0;for (int i 0; i s.length(); i) {sum s.charAt(i) * s.charAt(i);}Integer integer Integer.valueOf(sum);ListString list listMap.get(integer);if (null list) {list new ArrayList();}list.add(s);listMap.put(integer, list);}for (Map.EntryInteger, ListString value : listMap.entrySet()) {res.add(value.getValue());}return res;}思路1优化
优化的思路就是怎么得到每个单词的那个唯一值投机的方式就是再放大平方不行就立方依次往上果然4次方就通过了但是这种思路只能减小不能完全解决而且运算量也会增大。在美版leetcode上看到大神的思路用质数表示26个字母把字符串的各个字母相乘这样可保证字母异位词的乘积必定是相等的。这种原则上可以但是一些过长的字符串乘积值会溢出。public static ListListString groupAnagrams(String[] strs) {ListListString res new ArrayList();if (strs.length 0) {return res;}if (strs.length 1) {res.add(new ArrayList(Collections.singleton(strs[0])));return res;}int[] ints new int[]{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 listMap new HashMap();for (String s : strs) {long sum 1;for (int i 0; i s.length(); i) {sum * ints[s.charAt(i) - a];}Long integer Long.valueOf(sum);ListString list listMap.get(integer);if (null list) {list new ArrayList();}list.add(s);listMap.put(integer, list);}for (Map.EntryLong, ListString value : listMap.entrySet()) {res.add(value.getValue());}return res;
}思路2
先对每个字符串的从小到大排序含有相同字母排完序的就一致了以排完序的作为keyvalue放未排序的字符串列表public static ListListString groupAnagrams(String[] strs) {ListListString res new ArrayList();if (strs.length 0) {return res;}if (strs.length 1) {res.add(new ArrayList(Collections.singleton(strs[0])));return res;}MapString, ListString listMap new HashMap();for (String s : strs) {String sort s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString();ListString list listMap.get(sort);if (null list) {list new ArrayList();}list.add(s);listMap.put(sort, list);}for (Map.EntryString, ListString value : listMap.entrySet()) {res.add(value.getValue());}return res;}使用stream流操作 public static ListListString groupAnagrams(String[] strs) {return new ArrayList(Arrays.stream(strs).collect(Collectors.groupingBy(s - s.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());}
