Program Overview

This C program takes a list of strings and groups the anagrams together. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Program Structure

The program consists of the following key components:

• Includes and Definitions: Necessary header files and constants are defined.
• Sorting Function: A helper function that sorts the characters in each string to identify anagrams.
• Main Function: The main function reads input, processes the strings, and prints grouped anagrams.
• Data Structures: The program uses an array of strings to store the input and a map (using an array of linked lists) to store the groups of anagrams.

Code Implementation

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

#define MAX_STRINGS 100
#define MAX_LENGTH 100

// Function to compare two strings for sorting
int compare(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

// Function to sort a string
void sortString(char *str) {
    qsort(str, strlen(str), sizeof(char), compare);
}

// Function to group anagrams
void groupAnagrams(char *strs[], int strsSize) {
    // Array to hold sorted strings and their original counterparts
    char *sorted[MAX_STRINGS];
    char *anagrams[MAX_STRINGS][MAX_STRINGS];
    int count[MAX_STRINGS] = {0};

    for (int i = 0; i < strsSize; i++) {
        // Sort each string
        char *sortedStr = (char *)malloc(MAX_LENGTH * sizeof(char));
        strcpy(sortedStr, strs[i]);
        sortString(sortedStr);
        sorted[i] = sortedStr;

        // Grouping anagrams
        int found = 0;
        for (int j = 0; j <= i; j++) {
            if (j < i && strcmp(sorted[i], sorted[j]) == 0) {
                anagrams[j][count[j]] = strs[i];
                count[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            anagrams[i][0] = strs[i];
            count[i] = 1;
        }
    }

    // Print grouped anagrams
    for (int i = 0; i < strsSize; i++) {
        if (count[i] > 0) {
            for (int j = 0; j < count[i]; j++) {
                printf("%s ", anagrams[i][j]);
            }
            printf("\n");
        }
    }

    // Free allocated memory
    for (int i = 0; i < strsSize; i++) {
        free(sorted[i]);
    }
}

int main() {
    char *strs[MAX_STRINGS] = {
        "eat", "tea", "tan", "ate", "nat", "bat"
    };
    int strsSize = 6;

    printf("Grouped Anagrams:\n");
    groupAnagrams(strs, strsSize);

    return 0;
}
        

Explanation of the Code

1. Headers: The program includes standard libraries for input/output, string manipulation, and memory allocation.

2. compare Function: This function is used by qsort to compare two strings, facilitating sorting of characters in a string.

3. sortString Function: This function takes a string and sorts its characters using the standard library function qsort.

4. groupAnagrams Function: This is the core function that processes the list of strings. It sorts each string, groups anagrams together, and prints them.

• It first creates an array to store the sorted versions of the input strings.
• Then it groups the original strings based on their sorted versions.
• Finally, it prints each group of anagrams.

5. Main Function: This initializes an array of strings and calls the groupAnagrams function to display the grouped anagrams.

Conclusion

The program effectively groups anagrams by sorting the strings and using a simple comparison method. This solution demonstrates the use of fundamental C programming concepts, including arrays, strings, and dynamic memory allocation.