公积金门户网站建设方案,长沙房产信息网查询,企业运营实训报告,购物网站开发环境本文对应力扣高频100 ——49、字母异位词分组 哈希表最大的特点就是它可以把搜索元素的时间复杂度降到O(1)。这一题就是要我们找到 “字母异位词” 并把它们放在一起。
“字母异位词”就是同一个单词中字母的不同组合形式。判断“字母异位词”有两个视角#xff1a;1、所含字…本文对应力扣高频100 ——49、字母异位词分组 哈希表最大的特点就是它可以把搜索元素的时间复杂度降到O(1)。这一题就是要我们找到 “字母异位词” 并把它们放在一起。
“字母异位词”就是同一个单词中字母的不同组合形式。判断“字母异位词”有两个视角1、所含字母数量和种类相等的两个字符串数组互为“字母异位词”当我们将其排序后互为异位词的两个字符串应该是相同的2、字母出现次数相同的两个字符串数组互为“字母异位词”我们把其中字母出现的次数记录下来形成的数组应该是相同的。
方法一以重新排序后的字符串作为哈希表的key 思想所含字母数量和种类相等的两个字符串数组互为“字母异位词”当我们将其排序后互为异位词的两个字符串应该是相同的 public class Solution{public ListListInteger groupAnagrams(String[] strs){//如果字符串strs为空则返回一个空的数组if(strs null || str.length 0){return new ArrayList();}MapString,ListInteger map new HashMap();//遍历每一个元素for(String str : strs){//将strs中的元素从String类型转为char类型便于排序char[] charStr str.toCharArray();//将转为 字符数组 的元素进行排序Arrays.sort(charStr);//将排序后的字符数组转回String类型用于哈希比较String sortedStr new String(charStr);//如果哈希表中不包含当前元素就将其添加到哈希表中if(!map.containsKey(sortedStr)){map.put(sortedStr,new ArrayList());}//相反的如果哈希表中包含该元素就将其添加到对应key值的value值中//在本题中value值是一个数组map.get(sortedStr).add(str);}//返回最终数组return new ArrayList(map.values());}
} 方法二以字符出现次数作为哈希表的键 思想字母出现次数相同的两个字符串数组互为“字母异位词”我们把其中字母出现的次数记录下来形成的数组应该是相同的。 比如 “abc” 和 “bac” 互为字母异位词在这两个字符串中“a”、“b”、“c”各出现一次 public class Solution{public ListListInteger groupAnagrams(String[] strs){MapString,ListString map new HashMap();//遍历字符串数组中的每一个元素for(String str : strs){//定义一个count数组用于记录每个字母出现次数int[] count new int[26];//遍历元素中的每一个字母并将其记录到数组中for(char c : str.toCharArray()){count[c - a];}//将数组转为String类型便于放入哈希表String key Arrays.toString(count);//获取哈希表value值中的list数组ListString list map.getOrDefault(key,new ArrayList());//将原始元素str放入listlist.add(str);//将字母出现次数作为哈希表的key值list作为value值map.put(key,list);}//最后返回哈希表的valuereturn new ArrayList(map.values());}
}
