Group Anagrams

+10

Дан список слов strs. Два слова являются анаграммами, если одно можно получить перестановкой букв другого: буквы совпадают и каждая используется одинаковое количество раз. Сгруппируй каждое слово со всеми его анаграммами и верни по одной строке для каждой группы: слова группы в алфавитном порядке, разделённые одиночными пробелами. Расположи группы в алфавитном порядке по первому слову.

Если слово встречается дважды, оно указывается в своей группе дважды, а слово без анаграмм образует группу из одного слова. Алфавитный порядок означает порядок, как в словаре: aab идёт перед ab, а ab — перед abc.

Функция

groupAnagrams(strs: string-array) → string-array

strsstring-array: слова для группировки, только строчные буквы
Возвращаетstring-array: одна строка на группу: её слова отсортированы и соединены пробелами, группы упорядочены по их первому слову

Ограничения

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Каждое слово содержит только строчные английские буквы.

Примеры

Ввод: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Вывод: ["apple", "enlist listen silent", "notes onset stone tones"]
Пояснение: enlist, listen и silent используют по одному разу буквы e, i, l, n, s и t. В словах notes, onset, stone и tones есть буквы e, n, o, s и t, а apple ни с чем не совпадает. Если упорядочить группы по первому слову, получится apple, enlist, notes.

Ввод: strs = ["race", "arc", "care", "car", "acre"]
Вывод: ["acre care race", "arc car"]
Пояснение: acre, care и race содержат буквы a, c, e и r. В arc и car нет буквы e, поэтому они образуют собственную группу. acre идёт перед arc, потому что c стоит перед r на второй позиции.

Ввод: strs = ["b", "a", "b"]
Вывод: ["a", "b b"]
Пояснение: Две копии b являются анаграммами друг друга, и обе остаются в группе. У a нет пары, и она идет первой.

+15 скрытых тестов при отправке

Дополнительный вопрос

Предположим, что слова могут содержать любые символы Unicode, а не только 26 строчных букв. Какой из двух ключей — отсортированные буквы или количество букв — по-прежнему будет работать и что бы вы в нём изменили?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Сравнивать каждое слово со всеми остальными можно, но на каждую пару тратится полноценное сравнение. Решение задачи — канонический ключ: значение, которое вычисляется только по одному слову и одинаково для всех его анаграмм, но отличается для любого другого слова. Таким ключом служат буквы слова, отсортированные по порядку; хеш-таблица, сопоставляющая ключи группам, позволяет сгруппировать слова за один проход. Нужный порядок получается сам собой, если отсортировать слова перед группировкой.

Сравните каждое слово с каждой группой

Верно, но не успевает на самых больших тестах

Идея

Анаграммы обладают транзитивностью: если stone соответствует notes, а notes соответствует tones, то stone соответствует tones. Поэтому новому слову никогда не нужно соответствовать каждому участнику группы. Чтобы определить, принадлежит ли оно к этой группе, достаточно сравнить его с первым словом группы.

Чтобы сравнить два слова, подсчитайте буквы. Они являются анаграммами, если их длины совпадают и каждая буква встречается в одном столько же раз, сколько и в другом. Прибавьте 1 за каждую букву первого слова и вычтите 1 за каждую букву второго, а затем проверьте, что все 26 счётчиков равны 0.

Сначала отсортируйте входные данные — и порядок получится сам собой. Слова поступают в алфавитном порядке, каждое добавляется в конец своей группы, поэтому все группы остаются отсортированными. Группа создаётся, когда в неё поступает первое по алфавиту слово, поэтому сами группы уже упорядочены по первому слову.

Затраты приходятся на перебор. Если никакие два слова не являются анаграммами, каждое слово сравнивается со всеми предшествующими ему группами: 4000 слов дают около 4000 × 3999 / 2 ≈ 8 × 10^6 сравнений, каждое из которых затрагивает до 8 букв и 26 счётчиков. Для Python, Lua и R это слишком медленно на самых больших тестах, а объём работы растёт пропорционально квадрату длины списка, поэтому при 10^5 слов такой подход не подойдёт ни для какого языка.

Алгоритм

Отсортируйте слова в алфавитном порядке.
Храните список групп, каждая из которых представляет собой список слов.
Для каждого слова найдите группу, первое слово в которой содержит те же буквы в том же количестве, и добавьте слово в эту группу.
Если подходящей группы нет, создайте новую группу, содержащую только это слово.
Соедините слова в каждой группе одиночными пробелами и верните группы в том порядке, в котором вы их создали.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Группируйте по отсортированным буквам в хеш-таблице

Идея

Вместо того чтобы выяснять, к какой группе относится слово, вычислите название группы по самому слову. Отсортируйте буквы слова — все его анаграммы дадут одинаковую строку: listen, silent и enlist превратятся в eilnst, а stone — в enost. Два слова имеют одинаковую отсортированную форму тогда и только тогда, когда в них одни и те же буквы встречаются одинаковое количество раз, что и является определением анаграммы. Поэтому отсортированная форма — канонический ключ группы.

Хеш-таблица, сопоставляющая ключу список слов, группирует всё за один проход. Для каждого слова требуется одна сортировка не более чем 8 букв и один поиск в таблице; при этом слово никогда не сравнивается с другой группой.

Чтобы сохранить порядок, отсортируйте входные данные перед группировкой, как в первом подходе. Слова поступают в алфавитном порядке, поэтому каждый список заполняется по порядку, а ключ попадает в таблицу, когда поступает первое слово его группы. Таблицы, сохраняющие порядок вставки (словарь Python, Map в JavaScript, LinkedHashMap в Java, map в Dart, хеш-таблицы Ruby и массивы PHP), возвращают группы в этом порядке. Если таблица не сохраняет порядок, храните в ней индекс каждой группы, а сами группы — в списке.

Сортировка входных данных требует примерно n log n сравнений слов длиной до k букв — около 5 × 10^4 сравнений слов для 4000 слов вместо 8 × 10^6. Построение ключей добавляет O(n · k log k), что мало по сравнению с этим, поскольку k ≤ 8.

Алгоритм

Отсортируй слова в алфавитном порядке.
Для каждого слова создай ключ, отсортировав его буквы.
Найди ключ в хеш-таблице. Если он новый, создай для него пустую группу, сохраняя группы в порядке их создания.
Добавь слово в группу, соответствующую его ключу.
Верни слова каждой группы, разделённые одиночными пробелами, а группы — в порядке их создания.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Ловушки и крайние случаи

Группировка — это часть, которую нужно отработать. Большинство неправильных ответов в этой версии связаны с порядком вывода и с ключами, которые не являются уникальными.

Сортировка групп по ключу, а не по первому слову. Ключ — это наименьшая перестановка его букв, а не одно из слов: для ["cab", "bad"] ключи — abc и abd, поэтому первым будет cab, но при сортировке по первому слову раньше идёт bad.
Сбор слов в множество. Для ["b", "a", "b"] результат должен быть b b; множество хранит только один экземпляр.
Ключ, построенный только из уникальных букв. В ab и aabb используются одни и те же две буквы, но в aabb каждой из них по две, поэтому это не анаграммы.
Ключ, который складывает коды букв. У ad и bc одинаковая сумма, поэтому сумма объединяет слова, у которых нет общих букв.
Сортировка каждой группы, но не входных данных, с последующим забыванием отсортировать группы. В этом случае порядок вставки будет соответствовать порядку входных данных, а не первым словам.
Соединение вручную с пробелом в начале или конце строки группы.

Частые вопросы4

Какова временная сложность группировки анаграмм?

При использовании хеш-таблицы с ключами из отсортированных букв создание ключей занимает O(n · k log k) для n слов длиной до k букв, а работа с таблицей — O(n · k). В этой версии слова также сортируются, чтобы упорядочить результат, что добавляет O(n · k · log n). Для ключей и групп требуется O(n · k) памяти.

Ключ с подсчётом букв работает быстрее, чем сортировка каждого слова?

Ключ подсчёта — это 26 количеств букв, записанных текстом, например 1#0#2#…. Он требует времени O(k) вместо O(k log k), поэтому выигрывает на длинных словах. Для слов длиной не более 8 букв сортировка работает так же быстро, а алфавитная сортировка результата обходится дороже, чем вычисление любого из ключей. Оба ключа корректны, потому что два слова имеют одинаковые количества букв тогда и только тогда, когда у них одинаковый набор отсортированных букв.

Почему бы не использовать сумму кодов букв в качестве ключа?

Разные буквы могут давать одну и ту же сумму: a + d равно b + c, поэтому ad и bc попадут в одну группу. Ключ должен быть одинаковым для анаграмм и различаться для всего остального, и отсортированные буквы или полный подсчёт каждой буквы гарантируют это. Перемножение по одному простому числу на каждую букву также даёт точный результат, но при использовании 101 для z слово из десяти z уже переполняет 64-битное целое число.

Зачем сортировать входные данные перед группировкой?

В ответе требуются отсортированные группы, упорядоченные по их первому слову. Если отсортировать все слова один раз, получится и то и другое: каждая группа получит свои слова в алфавитном порядке, а группа будет создана, когда встретится её первое слово. Сортировка каждой группы после этого, а затем сортировка групп по их первому слову дают тот же результат, но требуют больше кода.

Python

def groupAnagrams(strs):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Ожидается

["apple", "enlist listen silent", "notes onset stone tones"]