Инопланетный словарь

Вы обнаружили инопланетный язык, который использует латинский алфавит. Но порядок букв в алфавите вам неизвестен.

Дан список строк words из инопланетного словаря, эти строки отсортированы в лексикографическом порядке согласно инопланетному алфавиту.

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

Строка s лексикографически меньше строки t, если в первой букве, в которой они отличаются, букваиз s идет перед буквой изt в инопланетном алфавите. Если первые min(s.length, t.length) бквы одинаковы, тогда s меньше тогда итольео тогда, если s.length < t.length.

Пример 1:

Дано: words = ["wrt","wrf","er","ett","rftt"]
Результат: "wertf"

Пример 2:

Дано: words = ["z","x"]
Результат: "zx"

Пример 3:

Дано: words = ["z","x","z"]
Результат: ""
Пояснение: Лексикографического порядка во входных данных нет, решения не существует - "".

Ограничения:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] состоят только из латинского алфавита.

Идея решения

Заметим:

По букве в слове мы не можем ничего сказать о позиции буквы в алфавите. Например, по слову kitten невозможно определить, идёт ли k перед i в алфавите.
Если во входном списке у нас есть ситуация, когда префикс находится после слова (например, abcd и потом ab), то мы сожем сказать, что решения не существует. Потому что в корректных алфавитах префиксы идут перед словами, которые их содержат.

Схематично можно решить задачу за три шага:

Определить правила зависимости по входным данным. Например, "A должно быть перед C", "X должно быть D", или "E должно быть B". Для этого сравниваем пары рядом стоящих слов, поскольку по условию задачи они идут в отсортированном порядке. Первая несовпадающая буква в паре слов в индексе j говорит о том, что эта буква (в индексе о) в слове 1 идет ПЕРЕД буквой в индексе j из слова 2.
Организовать эти зависимости в виде графа, где буквы - это вершины, а зависимости - это ребра. Можно использовать, например, список смежности. Мы будем строить реверсивный список смежности: каждой букве X мы ставим в соответствие спиок из букв, которые по алфовиту идет предположительно ПЕРЕД буквой Х.
Топологически отсортировать вершины графа. Это возможно, если в графе нет циклов. То есть обязательно должна быть вершины, не имеющие входящие ребра (листья или конец алфавита) и исходящие рёбра (корни, или начало алфавита). То есть мы берем любую зависимость, и вглубино просматриваем ее. Если мы доберемся до вершины без исходящих ребер, мы построили часть топологической цепочки. Если же мы дошли до вершины, которую ранее просматривали в этой цепочке зависимостей, то у нас имеется цикл - решения не существует.
Внимание: если мы рассмотрели одну зависимость и промаркировали какие-то буквы, как просмотренные, а потом перешли ко второй зависимости и опять попадаем на ранее просмотренную букву, то мы можем здесь не пересчитывать цепочку зависимостей, а сразу использовать результаты сканирования предыдущей зависимости. Цикл - это повторное попадание в букву в рамках поиска в глубину в одной зависимости.

В нашем примере 1 получим такие зависимости:

f->t, e->w, t->r, r->e

Имплементация

class Solution {

    private Map<Character, List<Character>> reverseAdjList = new HashMap<>();
    private Map<Character, Boolean> seen = new HashMap<>();
    private StringBuilder output = new StringBuilder();

    public String alienOrder(String[] words) {

        // Шаг 0: Найдем все уникальные буквы.
        for (String word : words) {
            for (char c : word.toCharArray()) {
                reverseAdjList.putIfAbsent(c, new ArrayList<>());
            }
        }

        // Шаг 1: строим граф зависимостей.
        for (int i = 0; i < words.length - 1; i++) {
// поскольку по условию входящий список уже отсортирован лексикографически,
// то мы можем рассматривать пары рядом стоящих слов
            String word1 = words[i];
            String word2 = words[i + 1];
            // word2 не должен быть префиксом слова word1.
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return ""; // иначе решения не существует по Замечанию 1            }
// Находим первое несовпадение и добавляем зависимость
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                if (word1.charAt(j) != word2.charAt(j)) {
// несовпадающая буква из word2 идет после несовпадающей буквы из слова word1                  reverseAdjList.get(word2.charAt(j)).add(word1.charAt(j));
                    break; // о дальнейших буквах мы не можем ничего утверждать по Замечанию 2, поэтому проверять их не имеет смысла.
                }
            }
        }

        // Шаг 2: DFS для построения ответа.
// нужно попытаться добраться до корня (начало алфавита)
        for (Character c : reverseAdjList.keySet()) {
            boolean result = dfs(c);
            if (!result) return "";
        }

        // не все уникальные буквы вошли в ответ, то есть решения нет
        if (output.length() < reverseAdjList.size()) {
            return "";
        }
        return output.toString();
    }

    // Возвращаем true iff нет циклов в графе зависимостей.
    private boolean dfs(Character c) {
        if (seen.containsKey(c)) {
            return seen.get(c); // ранее видели эту вершину:
// либо цикл, либо можем использовать результат, посчитанный для нее
        }
        seen.put(c, false);
        for (Character next : reverseAdjList.get(c)) {
            boolean result = dfs(next);
            if (!result) return false;
        }
        seen.put(c, true);
        output.append(c);
        return true;
    }
}

Анализ сложности

Сложность по времени : $O(C)$ . Здесь С - общая длинна строки, состоящей из всех входных слов, склеенных в одну строку.

Сложность по дополнительной памяти: $O(1)$ или $O(U + \min(U^2, N))$ , где U-количество уникальных букв (константа), N-слов в входном массиве строк.

Поиск по этому блогу

Coding interview scrapbook