49. Group Anagrams.txt

//Самый быстрый код на leetcode.
//ranges требует #include <ranges> который появился только в С++20.
//Создаём хеш-таблицу. Перебираем каждую строку во входном векторе. На каждой итерации создаём копию текщей рассматриваемой строки и сортируем её. Сортированная копия
//	строки является ключём. По этому ключу вставляем текущую строку в хеш-таблицу. Далее перебираем каждый ключ в получившейся хеш-таблице, и добавляем в вектор финального
//	ответа только значения строк по текущему ключу.
//auto - компилятор сам определяет тип переменной. 
//ranges - я так понял компилятор сам определяет дистацию действия оператора sort(что сортировать).
//move - какой то перенос объектов, пока ещё не разобрался.
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string>> output;//Вектор финального ответа.
        unordered_map<string, vector<string>> outputMap;//Создаём пустую Хеш-таблицу(карту), которая будет хранить группы анаграмм.

        for (const auto& s : strs)//Цикл по всем строкам вектора strs.
        {
            string sCopy {s}; //Иницилизируем переменную типа стринг и добавляем туда текущее (i-ое) значение строки вектора.
            ranges::sort(sCopy);//Сортируем символы строки sCopy. Без ranges мы можем сделать так: sort(sCopy.begin(), sCopy.end()).
            outputMap[sCopy].push_back(s);//Отсоритрованный sCopy является ключом. Вставляем в хеш-таблицу по этому ключу неотсортированную текущую исходную строку s.
        }

        for (auto& [_, x] : outputMap)//Перебераем каждый ключ в хештаблице. [_, x] означает что нас интересуют только вторые (second) значения, т.е. исходные строки s.
            output.push_back(move(x));//Добавляем ответ в вектор финального ответа. (move пока до конца не разобрал).
	
	/*Последний цикл можно написать так:
	for (auto x : outputMap)//Перебераем каждый ключ в хештаблице.
	    output.push_back(x.second);//Добавляем в вектор финального ответа только второе значение связки ключ-значение (т.е. исходные строки s).
	*/

        return output;//Возвращаем финальный вектор ответа.
    }
};



//Мой код. Очень медленный Runtime Beats 5.01% of users with C++ но по памяти хороший Memory Beats 81.84% of users with C++. ХЗ как так вышло.
//Я создаю копию исходного вектора, сортирую в каждой строке вектора символы, потом сравниваю каждую строку. Если строки копии вектора одинаковые, добавляю их 
//	оригинальные строки в ответ по индексу. Строки которые я уже использовал помечаю, чтобы их уже не использовать(".").

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> answer;
        vector<string> strsCopy = strs;
        for (int i = 0; i < strs.size(); i++)
            sort(strsCopy[i].begin(), strsCopy[i].end());
        for (int i = 0; i < strsCopy.size(); i++) {
            if (strsCopy[i] == ".")
                continue;
            vector<string> temp;
            string comp = strsCopy[i];
            for (int j = i; j < strsCopy.size(); j++) {
                if (comp == strsCopy[j]) {
                    temp.push_back(strs[j]);
                    strsCopy[j] = ".";
                }
            }
            answer.push_back(temp);
        }
        return answer;
    }
};