力扣00049.字母异位词分组

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟
字母异位词分组、数组、哈希表、字符串、排序、中等

题目描述

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

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

示例 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] 仅包含小写字母

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> anagrams_dict;
        for (const auto& word : strs) {
            string sorted_word = word;
            sort(sorted_word.begin(), sorted_word.end());
            anagrams_dict[sorted_word].push_back(word);
        }
        vector<vector<string>> result;
        for (const auto& entry : anagrams_dict) {
            result.push_back(entry.second);
        }
        return result;
    }
};

结果

执行用时 : 18 ms, 击败 98.21% 使用 C++ 的用户

内存消耗 : 22.84 MB, 击败 18.42% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> anagramsMap = new HashMap<>();
        for (String word : strs) {
            char[] charArray = word.toCharArray();
            Arrays.sort(charArray);
            String sortedWord = new String(charArray);
            anagramsMap.computeIfAbsent(sortedWord, k -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(anagramsMap.values());
    }
}

结果

执行用时 : 6 ms, 击败 89.04% 使用 Java 的用户

内存消耗 : 46.59 MB, 击败 24.25% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        anagrams_dict = defaultdict(list)
        for word in strs:
            sorted_word = ''.join(sorted(word))
            anagrams_dict[sorted_word].append(word)
        return list(anagrams_dict.values())

结果

执行用时 : 47 ms, 击败 46.09% 使用 Python 的用户

内存消耗 : 15.33 MB, 击败 94.22% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams_dict = defaultdict(list)
        for word in strs:
            sorted_word = ''.join(sorted(word))
            anagrams_dict[sorted_word].append(word)
        return list(anagrams_dict.values())

结果

执行用时 : 52 ms, 击败 % 使用 Python3 的用户

内存消耗 : 19.39 MB, 击败 % 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
#define MAX_STRING_LENGTH 102
typedef struct listnode {
    char key[MAX_STRING_LENGTH];
    int index[100];
    int count;
    int resultIndex;
    UT_hash_handle hh;
} Node;
int compareChars(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    if (strsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    Node* hashTable = NULL;
    *returnSize = 0;
    for (int i = 0; i < strsSize; i++) {
        char* sortedStr = (char*)malloc(sizeof(char) * (strlen(strs[i]) + 1));
        strcpy(sortedStr, strs[i]);
        qsort(sortedStr, strlen(sortedStr), sizeof(char), compareChars);
        Node* currentNode = NULL;
        HASH_FIND_STR(hashTable, sortedStr, currentNode);
        if (currentNode == NULL) {
            currentNode = (Node*)malloc(sizeof(Node));
            strcpy(currentNode->key, sortedStr);
            currentNode->count = 0;
            currentNode->resultIndex = (*returnSize)++;
            currentNode->index[(currentNode->count)++] = i;
            HASH_ADD_STR(hashTable, key, currentNode);
        } else {
            currentNode->index[(currentNode->count)++] = i;
        }
        free(sortedStr);
    }
    char*** result = (char***)malloc(sizeof(char**) * (*returnSize));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    Node *currentNode, *tempNode;
    HASH_ITER(hh, hashTable, currentNode, tempNode) {
        result[currentNode->resultIndex] = (char**)malloc(sizeof(char*) * (currentNode->count));
        for (int j = 0; j < currentNode->count; j++) {
            result[currentNode->resultIndex][j] = strdup(strs[currentNode->index[j]]);
        }
        (*returnColumnSizes)[currentNode->resultIndex] = currentNode->count;
        HASH_DEL(hashTable, currentNode);
        free(currentNode);
    }
    return result;
}

结果

执行用时 : 59 ms, 击败 64.66% 使用 C 的用户

内存消耗 : 26.71 MB, 击败 69.77% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        Dictionary<string, List<string>> anagramGroups = new Dictionary<string, List<string>>();
        foreach (var str in strs) {
            char[] charArray = str.ToCharArray();
            Array.Sort(charArray);
            string sortedStr = new string(charArray);
            if (!anagramGroups.ContainsKey(sortedStr)) {
                anagramGroups[sortedStr] = new List<string>();
            }
            anagramGroups[sortedStr].Add(str);
        }
        return new List<IList<string>>(anagramGroups.Values);
    }
}

结果

执行用时 : 154 ms, 击败 82.85% 使用 C# 的用户

内存消耗 : 72.99 MB, 击败 16.95% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const anagramGroups = {};
    for (const str of strs) {
        const sortedStr = str.split('').sort().join('');
        if (!anagramGroups[sortedStr]) {
            anagramGroups[sortedStr] = [];
        }
        anagramGroups[sortedStr].push(str);
    }
    return Object.values(anagramGroups);
};

结果

执行用时 : 112 ms, 击败 58.19% 使用 JavaScript 的用户

内存消耗 : 63.09 MB, 击败 5.02% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
function groupAnagrams(strs: string[]): string[][] {
    const anagramGroups: { [key: string]: string[] } = {};
    for (const str of strs) {
        const sortedStr = str.split('').sort().join('');
        if (!anagramGroups[sortedStr]) {
            anagramGroups[sortedStr] = [];
        }
        anagramGroups[sortedStr].push(str);
    }
    return Object.values(anagramGroups);
}

结果

执行用时 : 108 ms, 击败 79.49% 使用 TypeScript 的用户

内存消耗 : 63.50 MB, 击败 5.08% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    
    /**
     * @param String[] $strs
     * @return String[][]
     */
    function groupAnagrams($strs) {
        $anagramGroups = [];
        foreach ($strs as $str) {
            $sortedStr = $this->sortString($str);
            if (!isset($anagramGroups[$sortedStr])) {
                $anagramGroups[$sortedStr] = [];
            }
            $anagramGroups[$sortedStr][] = $str;
        }
        return array_values($anagramGroups);
    }
    private function sortString($str) {
        $charArray = str_split($str);
        sort($charArray);
        return implode('', $charArray);
    }
}

结果

执行用时 : 25 ms, 击败 84.62% 使用 PHP 的用户

内存消耗 : 24.56 MB, 击败 68.27% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var anagramGroups: [String: [String]] = [:]
        for str in strs {
            let sortedStr = String(str.sorted())
            if anagramGroups[sortedStr] == nil {
                anagramGroups[sortedStr] = []
            }
            anagramGroups[sortedStr]?.append(str)
        }
        return Array(anagramGroups.values)
    }
}

结果

执行用时 : 68 ms, 击败 96.37% 使用 Swift 的用户

内存消耗 : 18.21 MB, 击败 11.92% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
class Solution {
    fun groupAnagrams(strs: Array<String>): List<List<String>> {
        return strs.groupBy { it.toCharArray().sorted().joinToString("") }
            .values
            .toList()
    }
}

结果

执行用时 : 342 ms, 击败 50.00% 使用 Kotlin 的用户

内存消耗 : 46.57 MB, 击败 15.45% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  List<List<String>> groupAnagrams(List<String> strs) {
    Map<String, List<String>> anagramGroups = {};
    for (String str in strs) {
      String sortedStr = String.fromCharCodes(str.runes.toList()..sort());
      if (anagramGroups.containsKey(sortedStr)) {
        anagramGroups[sortedStr]!.add(str);
      } else {
        anagramGroups[sortedStr] = [str];
      }
    }
    return anagramGroups.values.toList();
  }
}

结果

执行用时 : 335 ms, 击败 82.61% 使用 Dart 的用户

内存消耗 : 149.44 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func groupAnagrams(strs []string) [][]string {
    anagramGroups := make(map[string][]string)
    for _, str := range strs {
        sortedStr := sortString(str)
        if _, ok := anagramGroups[sortedStr]; ok {
            anagramGroups[sortedStr] = append(anagramGroups[sortedStr], str)
        } else {
            anagramGroups[sortedStr] = []string{str}
        }
    }
    result := make([][]string, 0, len(anagramGroups))
    for _, group := range anagramGroups {
        result = append(result, group)
    }
    return result
}
func sortString(s string) string {
    charArray := []rune(s)
    sort.Slice(charArray, func(i, j int) bool {
        return charArray[i] < charArray[j]
    })
    return string(charArray)
}

结果

执行用时 : 15 ms, 击败 90.09% 使用 Go 的用户

内存消耗 : 7.60 MB, 击败 65.09% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
  anagram_groups = {}
  strs.each do |str|
    sorted_str = str.chars.sort.join
    if anagram_groups.key?(sorted_str)
      anagram_groups[sorted_str] << str
    else
      anagram_groups[sorted_str] = [str]
    end
  end
  anagram_groups.values
end

结果

执行用时 : 148 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 211.83 MB, 击败 62.50% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
object Solution {
  def groupAnagrams(strs: Array[String]): List[List[String]] = {
    val anagramGroups = strs.groupBy(str => str.sorted)
    anagramGroups.values.map(_.toList).toList
  }
}

结果

执行用时 : 691 ms, 击败 47.06% 使用 Scala 的用户

内存消耗 : 61.43 MB, 击败 17.65% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut anagram_groups: HashMap<String, Vec<String>> = HashMap::new();
        for str in strs {
            let sorted_str = sort_string(&str);
            if let Some(group) = anagram_groups.get_mut(&sorted_str) {
                group.push(str);
            } else {
                anagram_groups.insert(sorted_str, vec![str]);
            }
        }
        anagram_groups.values().cloned().collect()
    }
}
fn sort_string(s: &str) -> String {
    let mut char_array: Vec<char> = s.chars().collect();
    char_array.sort();
    char_array.into_iter().collect()
}

结果

执行用时 : 7 ms, 击败 91.25% 使用 Rust 的用户

内存消耗 : 4.77 MB, 击败 60.42% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户