leetCode49.字母异位词分组

题目描述

/**
     * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
     */

思路分析

1. 字母异位词，及他们所包含的每一个字符相同，但是排列顺序相同，要将这些排列顺序不同的字符串加入到同一个集合中，就要找出他们的相同点
2. 很明显，如果将他们按照一定的顺序排序（每一个从大到小或者从小到大），则得到的字符序列是一样的，再将字符序列转换为字符串，则这些字符串也相同
3. 因此他们的特征值就是这些相同的字符串
4. 再考虑如何存储这些字符异位词，因为最后以List的形式返回，所以很容易想到散列表
5. 使用散列表的键存储这些特征值，值存储字母异位词
6. 还有一个问题，就是如何将相同特征值的字符串添加到同一个集合中？
7. 使用HashMap集合的getOrDefault(Object key, V defaultValue)方法，返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。
8. 上述方法可以简单理解为如果key相同，则返回的是同一个值，也就是同一个集合
9. 然后将这些字母异位词加入到集合中，再将特征值和这个集合添加到HashMap中
10. 最后返回的是HashMap集合中的各个值，也就是各个集合
11. 可以遍历Hash集合然后将各个值添加到一个新集合，然后将新集合返回
12. 也可以直接调用HashMap的values方法拿到所有的值直接添加到集合中返回

代码及分析

public List<List<String>> groupAnagrams(String[] strs) {

        //使用HashMap存储，键存储字母异位词的相同点，值存储这一组异位词
        HashMap<String, List<String>> map = new HashMap<>();
        //遍历字符串数组
        for (String str : strs) {
            //将字符串转化为字符数组
            char[] chars = str.toCharArray();
            //调用排序方法
            Arrays.sort(chars);
            //将排序后的字符数组构成一个特征值字符串
            String s = new String(chars);

            //注意：
            //对这个方法的理解
            //getOrDefault(Object key, V defaultValue)
            //返回到指定键所映射的值，或 defaultValue如果此映射包含该键的映射。

            //即如果字符串s相同，返回的就是同一个list
            List<String> list = map.getOrDefault(s, new ArrayList<String>());
            //将具有相同特征的字符串添加
            list.add(str);
            //然后将特征值和list添加到map中
            map.put(s,list);
        }
        //最后将hashMap中的list以集合的形式返回
        return new ArrayList<List<String>>(map.values());

    }