Group Anagrams

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

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

СреднеХеширование Сортировка

+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 не совпадает ни с чем и, будучи первым словом, лидирует.

Ввод: 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 нет пары, и она стоит первой.

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

Если слова могут содержать любые символы Unicode, какой ключ — отсортированные символы или их количество — всё ещё будет работать и что бы вы в нём изменили?

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

Если никакие два слова не являются анаграммами, каждое слово проверяется на соответствие каждой предыдущей группе: 4000 слов дают около 8 × 10^6 сравнений, каждое из которых затрагивает до 8 букв и 26 счётчиков.

Алгоритм

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

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. Два слова имеют одинаковую отсортированную форму тогда и только тогда, когда в них одни и те же буквы встречаются одинаковое число раз, что и является определением анаграммы. Хеш-таблица, сопоставляющая ключу список слов, за один проход группирует все слова, и ни одно слово не сравнивается со словами из другой группы.

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

Сортировка входных данных требует примерно 5 × 10^4 сравнений слов для 4000 слов вместо 8 × 10^6.

Алгоритм

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

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 используются одни и те же две буквы, но это не анаграммы.
Сортировка каждой группы, но не входных данных и не самих групп. Тогда порядок вставки будет соответствовать входным данным, а не первым словам.

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

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

Построение ключей из отсортированных букв занимает 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-битного целого числа.

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

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

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