字母异位词分组

题目要求

编写一个函数，该函数接收一个字符串数组作为参数。函数的目的是将这个数组中的所有字母异位词分组。字母异位词指的是由相同字母以不同顺序组成的单词。例如，“listen”和“silent”就是一对字母异位词。函数需要将所有的字母异位词分到同一个子数组中。最终，函数返回一个数组，这个数组包含了所有分组后的子数组，子数组中的元素是字母异位词。返回的数组中的子数组可以按任意顺序排列。

解题思路

要解决这个问题，我们可以采取以下步骤：

1. 初始化一个空的哈希表：这个哈希表用于将具有相同字母组合的字符串分组。哈希表的键将是字符串中字母的某种统一形式（例如，按字典顺序排序后的字符串），值将是一个数组，存储所有具有相同字母组合的字符串。

2. 遍历字符串数组：对于数组中的每个字符串，我们将执行以下操作：

   • 将字符串中的字母排序，这样可以得到一个标准形式，用于检查两个字符串是否是字母异位词。例如，对于字符串 "eat"，排序后得到 "aet"。
   • 检查排序后的字符串是否已经作为键存在于哈希表中。如果存在，将原始字符串添加到对应的数组中。如果不存在，以排序后的字符串为键，创建一个新的数组，并将原始字符串添加到这个数组中。

3. 收集结果：遍历完成后，哈希表中的每个键都对应一个包含所有字母异位词的数组。将这些数组收集起来，形成一个列表，这个列表就是最终的结果。

4. 返回结果：返回步骤 3 中收集到的包含所有分组字母异位词的数组列表。

通过这种方法，我们可以确保所有的字母异位词都被分到了同一个组中，而且这个过程的时间复杂度相对较低，因为排序操作和哈希表的查找/插入操作通常都比较高效。

Golang 版本

package main

import (
	"fmt"
	"sort"
	"strings"
)

// 将字符串中的字符排序并返回
func sortString(s string) string {
	slice := strings.Split(s, "")
	sort.Strings(slice)
	return strings.Join(slice, "")
}

// 主函数，用于将字母异位词组合在一起
func groupAnagrams(strs []string) [][]string {
	anagrams := make(map[string][]string)
	for _, str := range strs {
		sortedStr := sortString(str)
		anagrams[sortedStr] = append(anagrams[sortedStr], str)
	}

	result := make([][]string, 0, len(anagrams))
	for _, group := range anagrams {
		result = append(result, group)
	}

	return result
}

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
	groupedAnagrams := groupAnagrams(strs)
	fmt.Println(groupedAnagrams)
}

这段代码定义了一个groupAnagrams函数，它接收一个字符串数组，并返回一个二维字符串数组，其中包含了分组后的字母异位词。主函数main展示了如何调用groupAnagrams函数并打印结果。

C++版本

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

// 将字符串中的字符排序并返回
std::string sortString(std::string s) {
    std::sort(s.begin(), s.end());
    return s;
}

// 主函数，用于将字母异位词组合在一起
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
    std::unordered_map<std::string, std::vector<std::string>> anagrams;
    for (const std::string& str : strs) {
        std::string sortedStr = sortString(str);
        anagrams[sortedStr].push_back(str);
    }

    std::vector<std::vector<std::string>> result;
    for (auto& pair : anagrams) {
        result.push_back(pair.second);
    }

    return result;
}

int main() {
    std::vector<std::string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
    std::vector<std::vector<std::string>> groupedAnagrams = groupAnagrams(strs);

    // 打印结果
    for (const auto& group : groupedAnagrams) {
        for (const std::string& str : group) {
            std::cout << str << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

这段代码定义了一个groupAnagrams函数，它接收一个字符串数组的引用，并返回一个二维字符串数组，其中包含了分组后的字母异位词。main函数展示了如何调用groupAnagrams函数并打印结果。在 C++中，使用std::unordered_map来存储键值对，其中键是排序后的字符串，值是原始字符串的列表。

Python 版本

from collections import defaultdict

def groupAnagrams(strs):
    anagrams = defaultdict(list)

    for s in strs:
        # Sort the string and use it as a key
        sorted_str = ''.join(sorted(s))
        anagrams[sorted_str].append(s)

    # Return the grouped anagrams as a list of lists
    return list(anagrams.values())

# Example usage
if __name__ == "__main__":
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(groupAnagrams(strs))

这段代码中，groupAnagrams 函数使用了 Python 的 defaultdict 来收集字母异位词。它将每个字符串排序后得到的结果作为键，原始字符串作为值添加到对应的列表中。最后，返回这个字典的值的列表，即分组后的字母异位词列表。在主函数中，我们定义了一个字符串列表，并调用 groupAnagrams 函数来打印分组后的结果。

Java 版本

import java.util.*;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<>());
            map.get(keyStr).add(s);
        }
        return new ArrayList<>(map.values());
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> groupedAnagrams = solution.groupAnagrams(strs);
        for (List<String> group : groupedAnagrams) {
            System.out.println(group);
        }
    }
}

这段 Java 代码定义了一个Solution类，其中包含了groupAnagrams方法，用于将字符串数组中的字母异位词分组。它使用了一个哈希表map来将排序后的字符串作为键，所有字母异位词作为值。main方法中创建了Solution的实例，并调用groupAnagrams方法，然后打印出分组后的字母异位词列表。

Rust 版本

use std::collections::HashMap;

fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut map: HashMap<String, Vec<String>> = HashMap::new();

    for s in strs.into_iter() {
        let mut chars: Vec<char> = s.chars().collect();
        chars.sort_unstable();
        let sorted_str: String = chars.into_iter().collect();
        map.entry(sorted_str).or_insert(Vec::new()).push(s);
    }

    map.into_values().collect()
}

fn main() {
    let strs = vec![
        "eat".to_string(),
        "tea".to_string(),
        "tan".to_string(),
        "ate".to_string(),
        "nat".to_string(),
        "bat".to_string(),
    ];
    let grouped_anagrams = group_anagrams(strs);

    for group in grouped_anagrams {
        println!("{:?}", group);
    }
}

这段 Rust 代码定义了一个group_anagrams函数，它接收一个字符串向量，并返回一个包含分组后字母异位词的向量。它使用了一个哈希表来将字符排序后的字符串作为键，所有字母异位词作为值。main函数中创建了一个字符串向量，并调用group_anagrams函数，然后打印出分组后的字母异位词列表。

总结

不同编程语言的解法核心思想相同，都是利用哈希表（或字典）来分组字母异位词。以下是解题步骤的总结：

1. 初始化哈希表：创建一个哈希表来存储分组信息，其中键是排序后的字符串，值是原始字符串的列表。

2. 遍历字符串数组：对于数组中的每个字符串，执行以下操作：

   • 将字符串的字符排序，以生成一个标准化的形式，这样所有的异位词都会有相同的排序字符串。
   • 检查排序后的字符串是否已经作为键存在于哈希表中。
     • 如果存在，将原始字符串添加到对应的值列表中。
     • 如果不存在，创建一个新的列表，并将原始字符串添加进去。

3. 收集分组：遍历完成后，哈希表中的每个键都对应一个包含所有字母异位词的列表。将这些列表收集起来，形成最终的分组列表。

在具体实现上，各编程语言有以下差异：

• Golang：使用map作为哈希表，通过字符串排序来作为键。
• C++：使用std::unordered_map作为哈希表，同样通过字符串排序来作为键。
• Python：使用defaultdict来简化哈希表的操作，利用排序后的字符串作为键。
• Java：使用HashMap作为哈希表，通过将字符串转换为字符数组并排序来获取键。
• Rust：使用HashMap作为哈希表，利用 Rust 的迭代器和收集器来处理字符串排序和分组。

所有解法都遵循了相同的算法逻辑，但是在语法和一些数据结构的使用上根据语言特性有所不同。