leetcode49-字母异位词分组
2020-12-14 / highPhone啊

这是leetcode题库的第49题 - 字母异位词分组

解题思路

解答前分析

根据题目意思：
  • 输入的数据全是小写字母，所以这道题目不必考虑大小写问题
  • 不用考虑输出的顺序
  • 输入为空的情况返回空的List

解题分析

  1. 异位词，可以看作是同一个字符串中字符的不同组合，所以，当所有异位词中的字符按照字母顺序重新排序后，肯定是相同的。
  2. 所有的异位词最终需要放到同一个数组中返回，考虑用ArrayList去存放同一组异位词
  3. 利用HashMap中key的唯一性，把2中的同类异位词放到HashMap中，key就是1中提到的字符数组排序后的值，这里注意要用String(不可变)做key，而非这个排序的字符数组
  4. 遍历入参的字符串数组，对于每个字符串元素，利用一个字符数组排序后，得到这个字符串的key，再去3中的HashMap中寻找，如果有找到这个key，证明前面已经有这个类别的异位词了，我们就把新的异位词添加到后面；如果没找到这个key，就新建一个ArrayList去存放这个异位词。
  5. 遍历完成后，我们就得到了一个分类好的HashMap，key是各个类别的异位词按字母顺序排列的字符串，value是这个类别的异位词数组，由于我们只关注value，所以只需要把value返回即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> groupString = new ArrayList<>();
        if(strs != null && strs.length > 0)//考虑空值输入
        {
            Map<String, List<String>> strMap = new HashMap<>();
            for (int i = 0; i < strs.length; i++) {
                char[] str = strs[i].toCharArray();//每个元素所属异位词的key
                Arrays.sort(str);//对当前元素的字符数组进行排序
                String strKey = String.valueOf(str);
                List<String> stringList = strMap.containsKey(strKey) ? strMap.get(strKey) : new ArrayList<>();//得到当前元素所属分类
                stringList.add(strs[i]);
                strMap.put(strKey, stringList);
            }
            groupString = new ArrayList<>(strMap.values());

        }
        return groupString;
    }
}

解答结果

更多题解

本文链接：https://highphone.xyz/29fb013c.html