Литокод Проблема: Групповые анаграммы
Задача:
Задав массив строк strs, сгруппируйте анаграммы. Вы можете вернуть ответ в любом порядке.
Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Шаблон: Массивы и хэширование
Подход:
- Создайте двумерный список для результата.
- Создайте HashMap: ключ = отсортированное слово, значение = список анаграмм.
- Итерация через массив входных строк и сортировка входных данных.
- Если отсортированный вход не находится в хэшмапе или крайний случай, когда отсортированный вход равен неотсортированному, то добавьте отсортированный вход как ключ, а неотсортированный вход как анаграмму.
- Если отсортированный вход уже существует как ключ в хэшмапе, то получите отсортированный ключ и добавьте неотсортированный вход в список анаграмм.
- Итерация по хэшмапе и добавление каждого списка анаграмм в список результатов. Верните результат.
Нотация 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;
}
}