C solution to LeetCode "Group Anagrams" problem (grouping anagrams in a two-dimensional array given an array of strings)

group-anagrams.c

/**
 * 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 HASH_SIZE 10000

typedef struct Node {
    char* key;
    char** list;
    int listSize;
    struct Node* next;
} Node;

Node* createNode(char* key, char* str) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = strdup(key);
    node->list = (char**)malloc(sizeof(char*));
    node->list[0] = strdup(str);
    node->listSize = 1;
    node->next = NULL;
    return node;
}

void addToList(Node* node, char* str) {
    node->listSize++;
    node->list = (char**)realloc(node->list, sizeof(char*) * node->listSize);
    node->list[node->listSize - 1] = strdup(str);
}

unsigned int hash(char* key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = ((hash << 5) + hash) + c;
    return hash % HASH_SIZE;
}

char* getKey(char* str) {
    int count[26] = {0};
    int len = strlen(str);
    if (len == 0) {
        char* key = (char*)malloc(1);
        key[0] = '\0';
        return key;
    }
    for (int i = 0; str[i]; i++)
        count[str[i] - 'a']++;
    char* key = (char*)malloc(200); // 53 bytes would suffice for normal English words but better to be safe
    int offset = 0;
    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            offset += sprintf(key + offset, "%c%d", i + 'a', count[i]);
        }
    }
    key[offset] = '\0';
    return key;
}

char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    Node* map[HASH_SIZE] = {0};
    int mapSize = 0;
    for (int i = 0; i < strsSize; i++) {
        char* key = getKey(strs[i]);
        unsigned int index = hash(key);
        Node* node = map[index];
        while (node && strcmp(node->key, key) != 0)
            node = node->next;
        if (node == NULL) {
            node = createNode(key, strs[i]);
            node->next = map[index];
            map[index] = node;
            mapSize++;
        } else {
            addToList(node, strs[i]);
        }
        free(key);
    }
    char*** result = (char***)malloc(sizeof(char**) * mapSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * mapSize);
    int j = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        Node* node = map[i];
        while (node) {
            result[j] = node->list;
            (*returnColumnSizes)[j] = node->listSize;
            j++;
            node = node->next;
        }
    }
    *returnSize = mapSize;
    return result;
}