49. Group Anagrams

Input:  strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

// 演算法 / Algorithm:
// 對每個字串算一個長度 26 的字母計數，編碼成「簽名」字串；
// 簽名相同 = 同組易位構詞。用簽名陣列分組（這裡用線性比對找已存在的簽名）。
// For each string, build a 26-letter count, encode it into a signature string;
// equal signatures = same anagram group. Group by matching signatures.

#include <stdlib.h>   // malloc / free / qsort
#include <string.h>   // strcmp / strlen / strcpy

// 比較函式給 qsort 用：把字串裡的字元由小到大排序
// Comparator for qsort: sorts characters ascending.
static int cmp_char(const void *a, const void *b) {
    // *(char*)a 把 void* 轉回 char* 再取值 / cast void* back to char* and dereference
    return (*(const char *)a) - (*(const char *)b);
}

// 回傳值：char***（指向「字串陣列的陣列」），即每組是一個 char**
// Returns char*** : an array of groups, each group being a char** (array of strings).
char ***groupAnagrams(char **strs, int strsSize,
                      int *returnSize, int **returnColumnSizes) {
    // keys[i] 存第 i 組的簽名；用來判斷新字串該歸到哪一組
    // keys[i] holds group i's signature, used to decide which group a string joins.
    char **keys   = (char **)malloc(sizeof(char *) * strsSize);   // 最多 strsSize 組 / at most strsSize groups
    char ***groups = (char ***)malloc(sizeof(char **) * strsSize); // 每組的字串清單 / list per group
    int *counts   = (int *)malloc(sizeof(int) * strsSize);         // 每組目前有幾個字串 / size of each group
    int groupCnt  = 0;                                             // 目前共幾組 / number of groups so far

    for (int i = 0; i < strsSize; i++) {
        // ---- 步驟 A：替 strs[i] 算簽名（排序它的字元複本）----
        // Step A: compute signature of strs[i] by sorting a copy of its chars.
        int len = (int)strlen(strs[i]);                 // 字串長度（不含結尾 ''）/ length excluding NUL
        char *sig = (char *)malloc(len + 1);            // +1 給字串結尾 '' / +1 for the terminator
        strcpy(sig, strs[i]);                           // 複製一份，避免改到原字串 / copy so we don't mutate input
        qsort(sig, len, sizeof(char), cmp_char);        // 原地排序字元 / sort chars in place -> signature

        // ---- 步驟 B：在已有的組裡找相同簽名 ----
        // Step B: search existing groups for a matching signature.
        int g = -1;                                     // -1 表示還沒找到 / -1 means not found yet
        for (int j = 0; j < groupCnt; j++) {
            if (strcmp(keys[j], sig) == 0) {            // strcmp==0 代表兩簽名相等 / equal signatures
                g = j;                                  // 找到所屬組別 / found the group index
                break;
            }
        }

        if (g == -1) {                                  // 沒有相同簽名 → 開新組 / no match -> new group
            g = groupCnt++;                             // 取一個新組編號 / allocate a new group id
            keys[g]   = sig;                            // 這組的簽名就是 sig（沿用，不再 free）/ keep sig as the key
            groups[g] = (char **)malloc(sizeof(char *) * strsSize); // 預留空間 / reserve room
            counts[g] = 0;                              // 新組目前 0 個元素 / starts empty
        } else {
            free(sig);                                  // 已有此組，sig 用不到了，釋放避免漏記憶體 / free unused copy
        }

        // ---- 步驟 C：把原始字串放進該組 ----
        // Step C: append the ORIGINAL string into its group.
        groups[g][counts[g]] = strs[i];                 // 存原字串指標 / store pointer to original string
        counts[g]++;                                    // 該組元素數 +1 / group size +1
    }

    // ---- 步驟 D：依 LeetCode 介面填寫回傳資訊 ----
    // Step D: fill the output parameters required by LeetCode.
    *returnSize = groupCnt;                             // 共幾組 / number of groups
    *returnColumnSizes = (int *)malloc(sizeof(int) * groupCnt); // 每組大小的陣列 / sizes array
    for (int j = 0; j < groupCnt; j++) {
        (*returnColumnSizes)[j] = counts[j];            // 第 j 組有幾個字串 / size of group j
        free(keys[j]);                                  // 簽名已用完，釋放 / signature no longer needed
    }

    free(keys);     // 釋放輔助陣列 / free helper arrays
    free(counts);
    return groups;  // groups 與其子陣列交給 LeetCode 管理 / hand groups to the harness
}

// 演算法 / Algorithm:
// 對每個字串把字元排序成「簽名」，用 unordered_map 以簽名為鍵收集字串。
// 最後把每個桶（bucket）搬進結果向量。
// Sort each string's chars into a signature; collect strings in an unordered_map
// keyed by signature; finally move each bucket into the result vector.

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>   // std::sort

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        // unordered_map：雜湊表，鍵=簽名，值=該簽名的字串清單
        // hash map: key = signature, value = list of strings with that signature.
        std::unordered_map<std::string, std::vector<std::string>> groups;

        // range-for：依序取出 strs 裡每個字串；const& 避免複製、且不修改原值
        // range-for over strs; const& avoids copying and forbids mutation.
        for (const std::string& s : strs) {
            std::string key = s;            // 複製一份當簽名來源 / copy to build the signature
            std::sort(key.begin(), key.end()); // 排序字元 → 簽名 / sort chars -> signature
            // groups[key] 若鍵不存在會自動建立空 vector，再 push_back 加入字串
            // operator[] auto-creates an empty vector if key is new, then we append.
            groups[key].push_back(s);
        }

        std::vector<std::vector<std::string>> result;   // 最終答案 / final answer
        result.reserve(groups.size());                  // 預留容量，減少重新配置 / reserve to avoid reallocs

        // 結構化綁定 [key, bucket]：把 map 的每個 pair 拆成鍵與值
        // structured binding splits each map entry into key and value.
        for (auto& [key, bucket] : groups) {
            // std::move：把 bucket 內容「搬」進結果，避免再複製一份字串
            // std::move transfers ownership instead of copying the vector.
            result.push_back(std::move(bucket));
        }
        return result;
    }
};