This document outlines a C++ program that groups anagrams from a list of strings. Anagrams are words that can be formed by rearranging the letters of another word, using all the original letters exactly once.

Program Structure

1. Include Necessary Headers: The program begins by including the necessary headers for input/output and data structures.
2. Function Declaration: A function named groupAnagrams is declared, which takes a vector of strings as input and returns a vector of vectors of strings.
3. Main Function: The main function initializes a list of strings and calls groupAnagrams to group the anagrams.
4. Sorting and Grouping: Within the groupAnagrams function, each string is sorted, and the sorted string is used as a key in an unordered map to group the anagrams.
5. Output: Finally, the grouped anagrams are printed to the console.

Program Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

/**
 * Groups anagrams from a list of strings.
 * 
 * @param strs A vector of strings to be grouped.
 * @return A vector of vector of strings containing grouped anagrams.
 */
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> anagramMap;

    // Iterate through each string in the input vector
    for (string str : strs) {
        // Sort the string to form a key
        string sortedStr = str;
        sort(sortedStr.begin(), sortedStr.end());
        
        // Group the original string by the sorted key
        anagramMap[sortedStr].push_back(str);
    }

    // Prepare the result vector to return
    vector<vector<string>> result;
    for (auto &pair : anagramMap) {
        result.push_back(pair.second);
    }
    
    return result;
}

int main() {
    // Initialize a list of strings
    vector<string> strings = { "eat", "tea", "tan", "ate", "nat", "bat" };
    
    // Group the anagrams
    vector<vector<string>> groupedAnagrams = groupAnagrams(strings);
    
    // Output the grouped anagrams
    for (const auto &group : groupedAnagrams) {
        for (const string &word : group) {
            cout << word << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Explanation of the Code

• Headers: The program uses iostream for input and output, vector for dynamic arrays, string for string manipulation, unordered_map for key-value storage, and algorithm for the sort function.
• Function groupAnagrams: This function takes a vector of strings as input. It creates an unordered map where the keys are sorted strings, and the values are vectors of the original strings that match the sorted key.
• Sorting: Each string is sorted using the sort function, which rearranges the characters in ascending order. This sorted string acts as a unique identifier for the group of anagrams.
• Storing Results: After processing all strings, the function constructs a result vector from the unordered map’s values, where each value is a group of anagrams.
• Main Function: This is where the program execution begins. It initializes a list of strings, calls the groupAnagrams function, and prints each group of anagrams.

Output

The program will output the grouped anagrams like this:

    eat tea ate
    tan nat
    bat

Conclusion

This C++ program effectively groups anagrams using sorting and a hash map. The time complexity of this solution is O(n * k log k), where n is the number of strings and k is the maximum length of a string. The space complexity is O(n) due to the storage of grouped anagrams.