Alien Dictionary

+10

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

Верните буквы, встречающиеся в словах, одной строкой в алфавитном порядке. Если списку соответствуют несколько порядков, верните тот, который идёт первым в обычном словарном порядке. Если ни один порядок не подходит, верните "invalid".

Функция

alienOrder(words: string-array) → string

wordsstring-array: слова, отсортированные в неизвестном алфавите
Возвращаетstring: буквы в наименьшем подходящем порядке или «недопустимо»

Ограничения

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Каждое слово содержит только строчные буквы английского алфавита.
То же слово может встречаться несколько раз. ТРЕБУЕМЫЙ ФОРМАТ ВЫВОДА: [Ваш переведённый текст здесь]

Примеры

Ввод: words = ["tea", "ten", "ate", "act", "cat"]
Вывод: "etacn"
Пояснение: tea и ten впервые различаются на буквах a и n, поэтому a стоит перед n. В остальных парах получается, что t стоит перед a, t — перед c, а a — перед c. Ни одно правило не упоминает e, поэтому в наименьшем порядке она стоит первой, затем идут t, затем a, а после них c и n, которые к тому моменту оба свободны; первой из них идёт c.

Ввод: words = ["bat", "tab", "tub", "bus"]
Вывод: "invalid"
Пояснение: bat перед tab ставит b перед t, tab перед tub ставит a перед u, а tub перед bus ставит t перед b. b перед t и t перед b не могут выполняться одновременно, поэтому ни один порядок не подходит.

Ввод: words = ["cooking", "cook"]
Вывод: "invalid"
Пояснение: cook — это начало слова cooking, поэтому в любом алфавите оно стоит первым. В списке оно стоит на втором месте, что нельзя объяснить никаким порядком букв.

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

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

Как определить, является ли порядок подгонки единственным?

Подсказки

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

Открыто 0 из 3

Решение

Список скрывает свой алфавит в тех местах, где соседние слова впервые различаются. Каждое такое место задаёт одно правило: буква x должна идти перед буквой y, а эти правила образуют ориентированный граф на буквах. Подходящий порядок — это топологический порядок этого графа. Список невозможно упорядочить по двум причинам: цикл среди правил и слово, стоящее перед своим собственным префиксом. Если на каждом шаге выбирать наименьшую доступную букву с помощью мин-кучи, получится наименьший подходящий порядок.

Попробуйте все возможные порядки букв

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

Идея

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

Теперь перебирайте перестановки от наименьшей к наибольшей. Начните с букв в алфавитном порядке — это наименьшая из всех перестановок — и каждый раз переходите к следующей по возрастанию (следующей перестановке). Первая перестановка, прошедшая проверку, будет наименьшим подходящим порядком. Если ни одна не подходит, верните "invalid".

Это решение корректно, но безнадёжно медленно на реальных входных данных. Для k букв существует k! перестановок: для 5 букв это 120, для 10 — 3,628,800, а для всех 26 — около 4 × 10^26. Каждая проверка читает весь список — всего C символов, до 5 × 10^4. На больших тестах наименьший подходящий порядок начинается с f или z, поэтому перед ним идёт астрономическое число перестановок, а если подходящего порядка нет, поиск должен проверить каждую из них.

Алгоритм

Собери различные буквы и отсортируй их по алфавиту.
Запиши позицию каждой буквы (её ранг) в текущем расположении.
Проверь каждую соседнюю пару: в первой отличающейся позиции буква первого слова должна иметь меньший ранг; если отличающихся позиций нет, первое слово не должно быть длиннее.
Если все пары проходят проверку, верни расположение. Иначе перейди к следующему большему расположению.
Если следующего расположения нет, верни "invalid".

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Алгоритм Кана с минимальной кучей

Идея

Извлекай правила из списка, а не угадывай порядок. Возьми два соседних слова и найди первую позицию, в которой они различаются. В tea и ten совпадают t и e, а различаются a и n, значит, a стоит перед n. В этом и состоит всё правило, которое даёт эта пара. Буквы после первого различия ничего не сообщают: act стоит перед cat, потому что a стоит перед c, а следующие за ними c и t в act никогда не сравниваются с a и t в cat. Поэтому каждая пара даёт не более одного правила — ребро от одной буквы к другой.

Пара без различающихся позиций — это ловушка с префиксом. Одно слово является началом другого, и в любом алфавите короткое слово должно идти первым. Порядок cook перед cooking допустим и не даёт никакого правила. Порядок cooking перед cook никогда не удастся отсортировать, поэтому сразу верни "invalid". Цикл, который лишь ищет различающиеся буквы, ничего не найдёт в этой паре и продолжит работу, чтобы вернуть порядок для списка, который не может породить ни один алфавит.

Теперь тебе нужен порядок букв, который соблюдает каждое ребро, — топологический порядок. Алгоритм Кана строит такой порядок. Подсчитай количество рёбер, входящих в каждую букву (её полустепень захода), помести букву с количеством 0, удали исходящие из неё рёбра и повторяй. У буквы в цикле всегда остаётся ребро от предыдущей буквы в цикле, поэтому её счётчик никогда не достигает 0, и её никогда не добавят в порядок. Если букв добавлено меньше, чем встречается в словах, значит, есть цикл, и ответ — "invalid".

Чтобы получить наименьший порядок, храни буквы со счётчиком 0 в мин-куче и всегда добавляй наименьшую. Этот жадный выбор безопасен. У первой буквы любого подходящего порядка счётчик равен 0, поэтому наименьшая из доступных букв — наименьшая возможная первая буква. Добавление этой буквы удаляет рёбра и никогда не блокирует другие буквы: все буквы, которые уже были доступны, остаются доступными. Тот же аргумент применим к второй позиции и так далее. В первом примере e и t доступны с самого начала, и первой идёт e. Обычная очередь тоже дала бы допустимый порядок, но не всегда наименьший.

Затраты: один проход по списку, всего C символов, чтобы найти первые различия. При k ≤ 26 буквах рёбер не больше k²; они хранятся в таблице k на k, поэтому повторяющееся правило записывается один раз, а в куче находится не больше k букв. Сложность — O(C + k²), на самых больших тестах это занимает несколько миллисекунд.

Алгоритм

Отметьте каждую букву, которая встречается в словах.
Для каждой пары соседних слов найдите первую позицию, в которой они различаются. Если такая позиция есть, добавьте ребро от буквы первого слова к букве второго слова один раз. Если такой позиции нет, а первое слово длиннее, верните "invalid".
Подсчитайте количество входящих рёбер для каждой буквы и поместите в минимальную кучу каждую встречающуюся букву, у которой это количество равно 0.
Извлеките наименьшую букву и добавьте её. Уменьшите количество для каждой буквы, на которую она указывает, и поместите в кучу все буквы, у которых это количество стало равно 0.
Если добавлено меньше букв, чем встречается в словах, верните "invalid". В противном случае верните добавленные буквы.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

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

Большинство неправильных ответов здесь остаются незамеченными: неверно прочитанное правило всё равно задаёт какой-то порядок, просто неправильный.

Использование более чем одного правила для пары слов. Учитывается только первая отличающаяся позиция. act перед cat означает, что a стоит перед c, и ничего не говорит о следующих за ней буквах.
Пропуск ловушки с префиксом. В словах cooking и cook нет отличающихся букв, поэтому цикл, который обрабатывает только различия, ничего не обнаружит и вернёт порядок. Ответ — "invalid".
Пропуск букв, которые не встречаются ни в одном правиле. В первом примере ни одно правило не упоминает e, но она должна быть в ответе, и в наименьшем порядке она стоит первой.
Использование обычной очереди вместо мин-кучи. Алгоритм Кана с очередью возвращает допустимый порядок, но по условию требуется наименьший.
Двойной учёт повторяющегося правила при подсчёте полустепени захода, но однократное сохранение его в графе. Тогда степень буквы так и не станет равной 0, и допустимый список будет ошибочно принят за цикл. Сохраняйте каждое правило один раз либо добавляйте и удаляйте его одинаковое число раз.
Принятие двух одинаковых соседних слов за ловушку с префиксом. Слово, за которым следует то же самое слово, находится в правильном порядке; невозможен только случай, когда более длинное слово стоит перед своим префиксом.

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

Какова временная сложность задачи Alien Dictionary?

O(C + k²), где C — общее количество символов в словах, а k ≤ 26 — количество различных букв. За один проход по списку находится первое различие в каждой соседней паре, а алгоритм Кана проходит не более чем по k² рёбрам. Мини-куча добавляет O(k log k), что мало по сравнению с остальным. Таблица рёбер занимает O(k²) памяти.

Почему сравнивать только соседние слова?

Упорядоченность транзитивна: если каждое слово не больше следующего, весь список упорядочен. Поэтому любое правило, которое можно вывести из двух далеко расположенных слов, уже следует из соседних пар между ними. Сравнение каждой пары слов не даёт дополнительной информации и требует O(n²) сравнений вместо n-1.

Почему выбор наименьшей готовой буквы дает наименьший порядок?

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

Почему слово перед собственным префиксом считается недопустимым?

В любом алфавите слово идёт после своего префикса, потому что при сравнении в более коротком слове раньше заканчиваются буквы, чем находится различие. Поэтому cooking перед cook — это нарушение порядка независимо от того, какие используются буквы, и никакое правило не может это исправить. Это единственный случай, когда список может быть невыполнимым, даже если среди его правил нет циклов.

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

words = ["tea", "ten", "ate", "act", "cat"]

Ожидается

"etacn"