leetcode49：字母异位词分组

题目链接

leetcode

题目描述

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

C++ 代码

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

/*
    哈希表：存储映射 (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(move(str));
        }

        vector<vector<string>> res;
        for (auto it = dict.begin(); it != dict.end(); it++) {
            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>> groups;
        for (const auto& str : strs) {
            // 对字符串进行编码，编码相同的字符串放在一个组
            string key = encode(str);
            groups[key].push_back(str);
        }

        vector<vector<string>> res;
        for (const auto& group : groups) {
            res.push_back(group.second);
        }

        return res;
    }

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

        // count 转换为字符串形式，比如 "a2b1c0..."
        string code;
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                char c = 'a' + i;
                code += c;
                code += to_string(count[i]);
            }
        }

        return code;
    }
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<string>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" << nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

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

    for (auto& strs : strs_cases) {
        vector<vector<string>> result = solution.groupAnagrams(strs);

        cout << "Input: ";
        printArray(strs);
        cout << endl;
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }
    
    return 0;
}