LC-49:字母异位词分组
我的实现思路:
思路:在实例中发现,对于不用的分组,他们所涉及的单词是一样的,尽管排列不同,所以抓住这一点,对所有的元素进行排序,最终将排好序的字符串,存放在HashMap中最为key,value就是ArrayList用于存放没有排序的但是字符串中包含的单词都是一样的字符串,初始化的时候只是创建了一个ArrayList。
// 创建一个HashMap,将每一个不同的字符串,排序后放在HashMap中。 HashMap<String, ArrayList<String>> hashMap = new HashMap<>(); for (int i = 0; i < strs.length; i++) { hashMap.put(order(strs[i]),new ArrayList<>()); }初始化好之后,HashMap中的数据就是这样的,以样例1为例:
key: aet value:空的ArrayList
key: ant value:空的ArrayList
key: ant value:空的ArrayList
key: abt value:空的ArrayList
然后对传递过来的字符串数组,在进行一个遍历,对每个遍历的元素,都进行排序,用排序后的字符串从HashMap中取值,取到ArrayList后,进行添加值,添加的就是没有排序的值。
最终,HashMap数据添加完毕。
最后,还需要创建一个List<List<String>>这个是中的结果集,我们还需要将HashMap中的数据,一个个遍历添加到中结果集中。
// 做好分组之后,需要将这几个分组整个在一个大的分组里面 List<List<String>> result = new ArrayList<>(); Set<String> keySet = hashMap.keySet(); for (String key : keySet) { ArrayList<String> arrayList = hashMap.get(key); result.add(arrayList); }
这个题的解题,一共包含两个方法:
1、对当前的这个字符串进行排序操作:
// 对这个字符串进行排序 private String order(String str) { char[] chars = str.toCharArray(); Arrays.sort(chars); return String.valueOf(chars); }2、就是利用HashMap的key-value原理,实现对不同的key进行ArrayList的存储。
class Solution { public List<List<String>> groupAnagrams(String[] strs) { // 创建一个HashMap,将每一个不同的字符串,排序后放在HashMap中。 HashMap<String, ArrayList<String>> hashMap = new HashMap<>(); for (int i = 0; i < strs.length; i++) { hashMap.put(order(strs[i]),new ArrayList<>()); } // 现在HashMap中已经有了该key,并且该key的value是ArrayList,所以下来就是对数组中的每一个字符串进行排序,然后对比时候是该key,若是的话,就添加到value中 for (int i = 0; i < strs.length; i++) { // 判断,如果该key是null,则就初始化,并且添加,若不为空,得到list后添加。 ArrayList<String> value = hashMap.get(order(strs[i])); value.add(strs[i]); } // 做好分组之后,需要将这几个分组整个在一个大的分组里面 List<List<String>> result = new ArrayList<>(); Set<String> keySet = hashMap.keySet(); for (String key : keySet) { ArrayList<String> arrayList = hashMap.get(key); result.add(arrayList); } return result; } }
我的完整实现代码:
class Solution { public List<List<String>> groupAnagrams(String[] strs) { // 创建一个HashMap,将每一个不同的字符串,排序后放在HashMap中。 HashMap<String, ArrayList<String>> hashMap = new HashMap<>(); for (int i = 0; i < strs.length; i++) { hashMap.put(order(strs[i]),new ArrayList<>()); } // 现在HashMap中已经有了该key,并且该key的value是ArrayList,所以下来就是对数组中的每一个字符串进行排序,然后对比时候是该key,若是的话,就添加到value中 for (int i = 0; i < strs.length; i++) { // 判断,如果该key是null,则就初始化,并且添加,若不为空,得到list后添加。 ArrayList<String> value = hashMap.get(order(strs[i])); value.add(strs[i]); } // 做好分组之后,需要将这几个分组整个在一个大的分组里面 List<List<String>> result = new ArrayList<>(); Set<String> keySet = hashMap.keySet(); for (String key : keySet) { ArrayList<String> arrayList = hashMap.get(key); result.add(arrayList); } return result; } // 对这个字符串进行排序 private String order(String str) { char[] chars = str.toCharArray(); Arrays.sort(chars); return String.valueOf(chars); } }