LeetCode 49、字母异位词分组

一、题目描述

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""] 输出: [[""]]

示例 3:

输入: strs = ["a"] 输出: [["a"]]

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

二、题目解析

三、参考代码

Java

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 字母异位词分组（LeetCode 49）：https://leetcode.cn/problems/group-anagrams/
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        // 互为字母异位词的两个字符串包含的字母相同
        // 因此两个字符串中的相同字母出现的次数一定是相同的
        // 可以将每个字母出现的次数使用字符串表示，作为哈希表的键
        Map<String, List<String>> map = new HashMap<String, List<String>>();

        for (String str : strs) {

            // 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
            // counts 代表每个小写字母出现的频次
            int[] counts = new int[26];

            // 利用 for 循环，统计 str 当中每个字母出现的频次
            for (int i = 0; i < str.length(); i++) {

                // 对于数组类型，其下标为 int 类型
                // 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
                // 比如 str.charAt(i) 是 b 字符，那么 b - a = 1，即 counts[1] 表示记录 b 出现的频次
                counts[str.charAt(i) - 'a']++;

            }

            // String 类是不可变类，即一旦一个 String 对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。
            // Java 提供了两个可变字符串类 StringBuffer 和 StringBuilder，中文翻译为“字符串缓冲区”
            // StringBuffer：线程安全
            // StringBuilder：线程不安全
            StringBuffer sb = new StringBuffer();

            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            for (int i = 0; i < 26; i++) {

                if (counts[i] != 0) {
                    
                    // 先记录字母，比如记录了字母 k
                    sb.append((char) ('a' + i));
                    // 再记录次数，比如记录了次数 9
                    sb.append(counts[i]);
                }
            }

            // 转换为字符串的形式，比如为 a1k9x7
            String key = sb.toString();

            // 在哈希表 map 当中找出这个 key 对应的字符串 str 来
            // 1、如果有这个 key，那么这个 key 对应的 数组 会新增一个 str 进去
            // 2、如果没有这个 key，那么会初始化一个数组，用来新增这个 str
            List<String> list = map.getOrDefault(key, new ArrayList<String>());

            // str 加入到 list 当中
            list.add(str);
            
            // map 进行更新
            map.put(key, list);

        }

        // 返回结果
        return new ArrayList<List<String>>(map.values());
    }
}

Python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 互为字母异位词的两个字符串包含的字母相同
        # 因此两个字符串中的相同字母出现的次数一定是相同的
        # 可以将每个字母出现的次数使用字符串表示，作为哈希表的键
        mp = collections.defaultdict(list)

        for s in strs:
            # counts 代表每个小写字母出现的频次
            counts = [0] * 26

            # 利用 for 循环，统计 str 当中每个字母出现的频次
            for c in s:
                counts[ord(c) - ord('a')] += 1

            # 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            key = ''.join(['#'+str(count) for count in counts])

            # 在哈希表 mp 当中找出这个 key 对应的字符串 str 来
            # 1、如果有这个 key，那么这个 key 对应的 数组 会新增一个 str 进去
            # 2、如果没有这个 key，那么会初始化一个数组，用来新增这个 str
            mp[key].append(s)

        # 返回结果
        return list(mp.values())

C++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 互为字母异位词的两个字符串包含的字母相同
        // 因此两个字符串中的相同字母出现的次数一定是相同的
        // 可以将每个字母出现的次数使用字符串表示，作为哈希表的键
        unordered_map<string, vector<string>> mp;

        for (string s : strs) {
            // counts 代表每个小写字母出现的频次
            vector<int> counts(26, 0);

            // 利用 for 循环，统计 str 当中每个字母出现的频次
            for (char c : s) {
                counts[c - 'a'] += 1;
            }

            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            stringstream keyStream;
            for (int count : counts) {
                keyStream << '#' << count;
            }
            string key = keyStream.str();

            // 在哈希表 mp 当中找出这个 key 对应的字符串 str 来
            // 1、如果有这个 key，那么这个 key 对应的 数组 会新增一个 str 进去
            // 2、如果没有这个 key，那么会初始化一个数组，用来新增这个 str
            mp[key].push_back(s);
        }

        // 返回结果
        vector<vector<string>> result;
        for (auto& p : mp) {
            result.push_back(p.second);
        }
        return result;
    }
};

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 26

// 哈希表结构体定义
typedef struct {
    char key[ALPHABET_SIZE * 4]; // 键：字母频率字符串
    char **values;              // 值：字符串数组
    int size;                   // 当前存储的值数量
    int capacity;               // 当前数组容量
} HashEntry;

typedef struct {
    HashEntry *entries;         // 哈希表条目
    int size;                   // 哈希表当前大小
    int capacity;               // 哈希表容量
} HashMap;

// 初始化哈希表
HashMap *initHashMap(int capacity) {
    HashMap *map = malloc(sizeof(HashMap));
    map->size = 0;
    map->capacity = capacity;
    map->entries = malloc(sizeof(HashEntry) * capacity);
    for (int i = 0; i < capacity; i++) {
        map->entries[i].key[0] = '\0';
        map->entries[i].values = NULL;
        map->entries[i].size = 0;
        map->entries[i].capacity = 0;
    }
    return map;
}

// 生成字母频率键
void generateKey(const char *str, char *key) {
    int counts[ALPHABET_SIZE] = {0};
    while (*str) {
        counts[*str - 'a']++;
        str++;
    }
    key[0] = '\0';
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        char temp[10];
        sprintf(temp, "#%d", counts[i]);
        strcat(key, temp);
    }
}

// 哈希表插入或更新
void insertToHashMap(HashMap *map, const char *key, const char *value) {
    for (int i = 0; i < map->size; i++) {
        if (strcmp(map->entries[i].key, key) == 0) {
            if (map->entries[i].size == map->entries[i].capacity) {
                map->entries[i].capacity = map->entries[i].capacity * 2 + 1;
                map->entries[i].values = realloc(map->entries[i].values, sizeof(char *) * map->entries[i].capacity);
            }
            map->entries[i].values[map->entries[i].size++] = strdup(value);
            return;
        }
    }
    if (map->size == map->capacity) {
        map->capacity *= 2;
        map->entries = realloc(map->entries, sizeof(HashEntry) * map->capacity);
    }
    HashEntry *entry = &map->entries[map->size++];
    strcpy(entry->key, key);
    entry->values = malloc(sizeof(char *) * 2);
    entry->values[0] = strdup(value);
    entry->size = 1;
    entry->capacity = 2;
}

// 获取哈希表中的所有值
char ***getHashMapValues(HashMap *map, int *returnSize, int **returnColumnSizes) {
    char ***result = malloc(sizeof(char **) * map->size);
    *returnColumnSizes = malloc(sizeof(int) * map->size);
    *returnSize = map->size;
    for (int i = 0; i < map->size; i++) {
        result[i] = map->entries[i].values;
        (*returnColumnSizes)[i] = map->entries[i].size;
    }
    return result;
}

// 主函数接口
char ***groupAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumnSizes) {
    HashMap *map = initHashMap(strsSize);
    char key[ALPHABET_SIZE * 4];
    for (int i = 0; i < strsSize; i++) {
        generateKey(strs[i], key);
        insertToHashMap(map, key, strs[i]);
    }
    return getHashMapValues(map, returnSize, returnColumnSizes);
}

Node JavaScript

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    // 创建一个哈希表存储结果
    const map = new Map();

    for (const str of strs) {
        // 统计字母频次
        const counts = new Array(26).fill(0);
        for (const char of str) {
            counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }

        // 构建键
        const key = counts.join("#");

        // 根据键存储到哈希表中
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(str);
    }

    // 返回结果
    return Array.from(map.values());
};

Go

func groupAnagrams(strs []string) [][]string {
    // 创建一个 map 存储结果
    hashMap := make(map[string][]string)

    for _, str := range strs {
        // 统计字母频次
        counts := make([]int, 26)
        for _, char := range str {
            counts[char-'a']++
        }

        // 构建键
        key := ""
        for _, count := range counts {
            key += fmt.Sprintf("#%d", count)
        }

        // 根据键存储到哈希表中
        hashMap[key] = append(hashMap[key], str)
    }

    // 将 map 的值转化为结果
    result := [][]string{}
    for _, group := range hashMap {
        result = append(result, group)
    }

    return result
}