2024-04-08

【LeeCode】刷题记录.md

作者：力扣官方题解
来源：力扣（LeetCode）

LeeCode热题100

49、字母异位词分组（中）

https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/

题面

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

为什么是哈希表相关的题？

思路：

当把单词中所有字母按照字母顺序表排列时，字母异位词的排序后的单词是相同的。
可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词。
哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。
具体做法：遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。

方法1：字母排序

构造单词的字符排序，作为键。
将单词加入散列表。
返回答案。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

复习

char[] toCharArray() 。将此字符串转换为新的字符数组。
getOrDefault。HashMap的一个方法，返回指定键映射到的值，如果此映射不包含键的映射，则返回 defaultValue 。
向list中新增元素用add方法。
向哈希表中新增元素用put方法，同时传入键和值。

复杂度分析

方法2：计数

互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。
首先统计字符的出现顺序，然后构造键，把具有相通特征的字符串的单词们放在一组，最后返回结果。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer(); 	//可变字符串对象
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

复杂度分析

面试要点

通过分析，能否意识到单词和键的映射关系。
利用散列表高效储存结果。
数据结构和常见的库函数。