【算法题解】25. 字母异位词分组

小半 • 2023年12月28日上午11:53 • 数据结构 • 阅读 200

这是一道 「简单」 题

https://leetcode.cn/problems/group-anagrams/description/

题目描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

仅包含小写字母

解题思路

将字符串排序，如果排序后的字符串是一样的就是字母异位词。

可以使用哈希表这类数据结构，key 存排序后的字符串，value 存排序后一样的原字符串列表。

逻辑非常简单，循环遍历给定字符串列表，并对每一个字符串排序，将排序结果和原字符串存放到哈希表中，具体实现看代码。

Java 代码实现

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> cache = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String sorted = new String(ch);
            if(!cache.containsKey(sorted)){
                cache.put(sorted, new ArrayList<>());
            }
            cache.get(sorted).add(str);
        }
        return new ArrayList<List<String>>(cache.values());
    }
}

Go 代码实现

func groupAnagrams(strs []string) [][]string {

    cache := make(map[string][]string)

    for _, str := range strs {
        s := []byte(str)
        sort.Slice(s, func(i int, j int) bool {
         return s[i] < s[j]
        })
        sorted := string(s)
        cache[sorted] = append(cache[sorted], str)
    }

    ans := make([][]string, 0)
    
    for _, value := range cache {
        ans = append(ans, value)
    }
    
    return ans
}