leetcode49：字母异位词分组

题目链接

leetcode

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 辅助函数：打印输入结果
void printInput(const vector<string>& input) {
    cout << "[";
    for (const string& word : input) {
        cout << word << ",";
    }
    cout << "]";
}

// 辅助函数：打印输出结果
void printOutput(const vector<vector<string>>& output) {
    for (const auto& group : output) {
        cout << "[";
        for (const string& word : group) {
            cout << word << ",";
        }
        cout << "], ";
    }
}

/*
    哈希表：存储映射 (string, vector<string>)
    将每个字符串的所有字符从小到大排序，
    将排好序的字符串作为 key，然后将原字符串放入 key 对应的 value。

    时间复杂度：O(nklogk)
        n 是字符串个数，k 是字符串平均长度。
        对于每个字符串，哈希表和数组的插入操作复杂度都是 O(1)，排序复杂度是 O(klogk)。
    空间复杂度：O(nk)
*/
class Solution_0 {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> dict;
        for (const auto& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            // dict[key].push_back(str);
            dict[key].push_back(move(str));
        }

        vector<vector<string>> res;
        for (auto it = dict.begin(); it != dict.end(); it ++) {
            // res.push_back(it->second);
            res.push_back(move(it->second));
        }

        return res;
    }
};

/*
    异位词这类问题的关键：
        如何快速地判断两个字符串是异位词，考察数据编码和哈希表的使用。
    
    异位词的编码问题，对字符串排序可以是一种编码方案。
    但是这样时间复杂度略高，而且会修改原始数据。
    更好的方案是，使用每个字符的出现次数进行编码。

    时间复杂度：O(nk)
        n 是字符串个数，k 是字符串平均长度。
    空间复杂度：O(nk)
*/
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> codeGroup; // 编码到分组的映射
        for (const string& s : strs) {
            // 对字符串进行编码，把编码相同的字符串放在一起
            string code = encode(s);
            codeGroup[code].push_back(s);
        }
        
        vector<vector<string>> res;
        for (const auto& group : codeGroup) {
            res.push_back(group.second);
        }

        return res;
    }

    // 编码方法：每个字母的出现次数
    string encode(string str) {
        vector<char> count(26, 0);
        for (const char& c : str) {
            int delta = c - 'a';
            count[delta] ++;
        }
        string code(count.begin(), count.end());
        return code;
    }
};

int main() {
    Solution solution;
    vector<vector<string>> testCases = {
        {"eat", "tea", "tan", "ate", "nat", "bat"},
        {"", ""},
        {"a"},
    };

    for (auto& testCase : testCases) {
        // 调用 groupAnagrams 函数
        vector<vector<string>> result = solution.groupAnagrams(testCase);
        // 输出结果
        cout << "Input: ";
        printInput(testCase);
        cout << endl;
        cout << "Output: ";
        printOutput(result);
        cout << endl;
    }
    
    return 0;
}

Golang 代码

package main

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

// compare2DStringSlices 比较两个二维字符串切片是否相等
func compare2DStringSlices(a, b [][]string) bool {
	if len(a) != len(b) {
		return false
	}

	// 对内层切片排序
	for _, group := range a {
		slices.Sort(group)
	}
	for _, group := range b {
		slices.Sort(group)
	}

	// 对外层切片排序
	sort.Slice(a, func(i, j int) bool {
		return strings.Join(a[i], ",") < strings.Join(a[j], ",")
	})
	sort.Slice(b, func(i, j int) bool {
		return strings.Join(b[i], ",") < strings.Join(b[j], ",")
	})

	// 逐个比较排序后的二维切片
	for i := range a {
		if len(a[i]) != len(b[i]) {
			return false
		}
		if !slices.Equal(a[i], b[i]) {
			return false
		}
	}
	return true
}

/*
	哈希表：存储映射。
	遍历字符串数组，将每个字符串的所有字符从小到大排序，
	将排序后的字符串作为 key，原字符串作为 value 存入哈希表。
	最后，将映射中的值转换为二维切片并返回。

	时间复杂度：O(nklogk)
		n 是字符串个数，k 是字符串平均长度。
		对于每个字符串，哈希表和数组的插入操作复杂度都是 O(1)，排序复杂度是 O(klogk)。
	空间复杂度：O(nk)
*/
func groupAnagrams_0(strs []string) [][]string {
	// mp := map[string][]string{}
	mp := make(map[string][]string)

	for _, str := range strs {
		// 将字符串转换为字符数组并排序
		chars := strings.Split(str, "")
		slices.Sort(chars)
		sortedStr := strings.Join(chars, "")

		// 将排序后的字符串为键，原始字符串为值添加到映射中
		mp[sortedStr] = append(mp[sortedStr], str)
	}
	// 将映射中的值转换为二维切片并返回
	res := make([][]string, 0, len(mp))
	for _, v := range mp {
		res = append(res, v)
	}

	return res
}

/*
	字符频率计数：
		对于每个字符串，使用一个长度为 26 的整数数组 count，记录每个字母的出现次数。
	键的生成：
		将字符频率计数器转换为一个唯一的字符串表示，作为哈希表的键。
		这个键包含了每个字母及其出现次数的信息，因此不同的字母异位词将具有相同的键。
	分组存储：
		使用一个哈希表（map）来存储分组，键是字符频率的字符串表示，值是字母异位词的列表。
		遍历字符串数组，将每个字符串添加到对应的分组中。
	结果转换：
		最后，将哈希表中的所有分组转换为一个二维字符串切片，作为最终的输出结果。

	时间复杂度：O(nk)
		n 是字符串个数，k 是字符串平均长度。
	空间复杂度：O(nk)
*/
func groupAnagrams(strs []string) [][]string {
    mp := make(map[string][]string)

    for _, str := range strs {
        // 初始化字符频率
        count := make([]int, 26)
        for _, ch := range str {
            count[ch-'a']++
        }
        // 将字符计数转换为字符串，作为哈希表的键
        var keyBuilder strings.Builder
        for i, c := range count {
            keyBuilder.WriteString(fmt.Sprintf("%c%d", 'a'+i, c))
        }
        key := keyBuilder.String()
		// 将原字符串添加到对应的分组中
		mp[key] = append(mp[key], str)
    }

	// 将 map 中的分组转换为二维切片
    res := make([][]string, 0, len(mp))
    for _, group := range mp {
        res = append(res, group)
    }
    return res;
}

func main() {
	// 测试用例
	testCases := []struct {
		strs     []string
		expected [][]string
	}{
		{
			strs:     []string{"eat", "tea", "tan", "ate", "nat", "bat"},
			expected: [][]string{{"bat"}, {"nat","tan"}, {"ate","eat","tea"}},
		},
		{
			strs:     []string{""},
			expected: [][]string{{""}},
		},
		{
			strs:     []string{"a"},
			expected: [][]string{{"a"}},
		},
	}

	for i, tc := range testCases {
		result := groupAnagrams(tc.strs)
		fmt.Printf("Test Case %d, Input: strs = %v\n", i+1, tc.strs)

		if compare2DStringSlices(result, tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}