Дано: массив строк strs, сгруппируйте строки по спискам в соответствии, являются ли они анаграммами или нет. Вы можете вернуть ответ в любом порядке.
Анаграмма - это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример 1:
Дано: strs = ["eat", "tea", "tan", "ate", "nat", "bat"].
Ответ: [["bat"],["nat","tan"],["ate","eat","tea"]]
Пример 2:
Дано: strs = [""]
Ответ: [[""]]
Пример 3:
Дано: strs = ["a"]
Ответ: [["a"]]
Ограничения:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] состоит из строчных английских букв.
Решение: с использованием хэш-таблицы
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = defaultdict(list)
for s in strs:
key = "".join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
Используем defaultdict. Это подкласс обычного словаря (dict), который позволяет задать значение по умолчанию для несуществующих ключей.
Создается словарь defaultdict, в котором каждое значение инициализируется как список. Это позволяет добавлять новые элементы в список без предварительной проверки существования ключа.
Функция выполняет итерацию по каждой строке s в предоставленном списке strs. Внутри цикла строка s сортируется по алфавиту с помощью sorted(s), которая возвращает список символов, а затем ''.join(sorted(s)) используется для преобразования списка символов обратно в строку. Эта отсортированная строка служит ключом в нашем словаре.
Исходная несортированная строка s добавляется к списку в словаре, соответствующему отсортированному ключу (k). Это означает, что все анаграммы s будут сгруппированы под одним ключом.
После обработки всех строк в strs функция возвращает значения словаря в виде списка списков, где каждый подсписок содержит все анаграммы определенного слова из входного списка.
Временная сложность
Цикл даёт сложность O(m) и сортировка даёт сложность O(nlog n) = O(m * n log n).
Пространственная сложность: Мы создаём список списков, а это O(n*m)