Question

How to convert an array of strings and group all the anagrams into subarrays in C

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Structure to hold a group of anagrams
typedef struct {
    char **words;   // Array of words in this group
    int count;      // Number of words
} AnagramGroup;

// Function to sort characters in a string (used to generate key)
void sortString(char *str) {
    int len = strlen(str);
    
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] > str[j]) {
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
            }
        }
    }
}

void freeGroups(AnagramGroup *groups, int groupCount) {
    if (!groups) return;
    
    for (int i = 0; i < groupCount; i++) {
        for (int j = 0; j < groups[i].count; j++) {
            free(groups[i].words[j]);
        }
        free(groups[i].words);
    }
    
    free(groups);
}

// Safe strdup with error check
char* safe_strdup(const char *s) {
    char *copy = strdup(s);
    if (!copy) {
        fprintf(stderr, "Memory allocation failed in strdup\n");
        exit(EXIT_FAILURE);
    }
    
    return copy;
}

// Function to check if two strings are anagrams
int areAnagrams(const char *s1, const char *s2) {
    if (strlen(s1) != strlen(s2)) return 0;
    
    char *copy1 = safe_strdup(s1);
    char *copy2 = safe_strdup(s2);
    
    sortString(copy1);
    sortString(copy2);
    
    int result = strcmp(copy1, copy2) == 0;
    
    free(copy1);
    free(copy2);
    
    return result;
}

AnagramGroup* groupAnagrams(char **words, int wordCount, int *groupCount) {
    AnagramGroup *groups = NULL;
    *groupCount = 0;

    for (int i = 0; i < wordCount; i++) {
        int found = 0;
        for (int g = 0; g < *groupCount; g++) {
            if (areAnagrams(words[i], groups[g].words[0])) {
                // Add to existing group
                char **tmp = realloc(groups[g].words, (groups[g].count + 1) * sizeof(char*));
                if (!tmp) {
                    fprintf(stderr, "Memory allocation failed in realloc\n");
                    freeGroups(groups, *groupCount);
                    exit(EXIT_FAILURE);
                }
                groups[g].words = tmp;
                groups[g].words[groups[g].count] = safe_strdup(words[i]);
                groups[g].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            // Create new group
            AnagramGroup *tmpGroups = realloc(groups, (*groupCount + 1) * sizeof(AnagramGroup));
            if (!tmpGroups) {
                fprintf(stderr, "Memory allocation failed in realloc (groups)\n");
                freeGroups(groups, *groupCount);
                exit(EXIT_FAILURE);
            }
            groups = tmpGroups;

            groups[*groupCount].words = malloc(sizeof(char*));
            if (!groups[*groupCount].words) {
                fprintf(stderr, "Memory allocation failed in malloc (words)\n");
                freeGroups(groups, *groupCount);
                exit(EXIT_FAILURE);
            }
            groups[*groupCount].words[0] = safe_strdup(words[i]);
            groups[*groupCount].count = 1;
            (*groupCount)++;
        }
    }
    
    return groups;
}

int main() {
    char *words[] = {"eat", "tea", "rop", "ate", "nat", "orp", "tan", "bat", "pro"};
    int wordCount = sizeof(words) / sizeof(words[0]);

    int groupCount;
    AnagramGroup *groups = groupAnagrams(words, wordCount, &groupCount);

    // Print groups
    printf("Anagram Groups:\n");
    for (int i = 0; i < groupCount; i++) {
        printf("[ ");
        for (int j = 0; j < groups[i].count; j++) {
            printf("%s ", groups[i].words[j]);
        }
        printf("]\n");
    }

    freeGroups(groups, groupCount);
    
    return 0;
}



/*
run:

Anagram Groups:
[ eat tea ate ]
[ rop orp pro ]
[ nat tan ]
[ bat ]

*/

 

70+ SQL courses for beginners and professionals