Групповые анаграммы

Литокод Проблема: Групповые анаграммы

Задача:

Задав массив строк strs, сгруппируйте анаграммы. Вы можете вернуть ответ в любом порядке.

Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Шаблон: Массивы и хэширование

Подход:

1. Создайте двумерный список для результата.
2. Создайте HashMap: ключ = отсортированное слово, значение = список анаграмм.
3. Итерация через массив входных строк и сортировка входных данных.
4. Если отсортированный вход не находится в хэшмапе или крайний случай, когда отсортированный вход равен неотсортированному, то добавьте отсортированный вход как ключ, а неотсортированный вход как анаграмму.
5. Если отсортированный вход уже существует как ключ в хэшмапе, то получите отсортированный ключ и добавьте неотсортированный вход в список анаграмм.
6. Итерация по хэшмапе и добавление каждого списка анаграмм в список результатов. Верните результат.

Нотация Big-O:

Временная сложность: O(m * nlog(n)).
Мы итерируем n раз для каждой строки.
Мы сортируем каждую строку с помощью Arrays.sort(), что составляет O(n log(n)).

Пространственная сложность: O(n * m)
Мы используем дополнительные структуры данных для хранения.
У нас есть двумерный список для хранения результата.
Для хранения элементов у нас есть хэшмап.

Код:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // input: string array 
        // output: 2D list 
        List<List<String>> result = new ArrayList<List<String>>();

        Map <String, List<String>> hashMap = new HashMap<>();

        for(String str : strs){
            char [] array = str.toCharArray();
            Arrays.sort(array);

            String sortStr = str.valueOf(array);

            // edge case if current == key then add to key. 
            if(sortStr == str || !hashMap.containsKey(sortStr)){
                List <String> anagram = new ArrayList<>();
                anagram.add(str);
                hashMap.put(sortStr, anagram);
            } else {
                hashMap.get(sortStr).add(str);
            }
        }

        // add anagram list into result 
        for(String s : hashMap.keySet()){
            result.add(hashMap.get(s));
        }

        return result;
    }
}