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

ゝ一世哀愁。 2024-03-23 13:40 59阅读 0赞

#### 文章目录 ####

*   *  题目描述
     *  解题思路
     *   *   *  Java 代码实现
             *  Go 代码实现
     *  复杂度分析

> 这是一道 **简单** 题  
> 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"]]

**提示：**

*   1 < = s t r s . l e n g t h < = 1 0 4 1 <= strs.length <= 10^4 1<=strs.length<=104
 *   0 < = s t r s \[ i \] . l e n g t h < = 100 0 <= strs\[i\].length <= 100 0<=strs\[i\].length<=100
 *   s t r s \[ i \] strs\[i\] strs\[i\] 仅包含小写字母

### 解题思路 ###

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

可以使用哈希表这类数据结构，`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
    }

### 复杂度分析 ###

*  **时间复杂度**： O ( n k ) O(nk) O(nk)，`n` 为给定字符串数组的长度，`k` 为字符串排序的时间复杂度。
 *  **空间复杂度**： O ( n ) O(n) O(n), `n`为给定字符串数组的长度， 哈希表`value`总共存放有`n`个字符串。