Задача: 269. Alien Dictionary
Сложность: hard

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

Пример:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

👨‍💻 Алгоритм:

1⃣Извлечение отношений порядка и создание списков смежности:
Извлечь отношения порядка между буквами из слов.
Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого.

2⃣Подсчет числа входящих ребер:
Подсчитать количество входящих ребер (in-degree) для каждой буквы.
Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы.

3⃣Обход в ширину (BFS):
Инициализировать очередь буквами с нулевым in-degree.
Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

function alienOrder($words) {
    $adjList = [];
    $inDegree = [];

    foreach ($words as $word) {
        foreach (str_split($word) as $char) {
            $inDegree[$char] = 0;
        }
    }

    for ($i = 0; $i < count($words) - 1; $i++) {
        $firstWord = $words[$i];
        $secondWord = $words[$i + 1];
        for ($j = 0; $j < min(strlen($firstWord), strlen($secondWord)); $j++) {
            $c = $firstWord[$j];
            $d = $secondWord[$j];
            if ($c !== $d) {
                if (!isset($adjList[$c])) {
                    $adjList[$c] = [];
                }
                if (!in_array($d, $adjList[$c])) {
                    $adjList[$c][] = $d;
                    $inDegree[$d]++;
                }
                break;
            }
        }
        if (strlen($secondWord) < strlen($firstWord) && strpos($firstWord, $secondWord) === 0) {
            return "";
        }
    }

    $output = [];
    $queue = [];

    foreach ($inDegree as $char => $degree) {
        if ($degree == 0) {
            $queue[] = $char;
        }
    }

    while (!empty($queue)) {
        $c = array_shift($queue);
        $output[] = $c;
        if (isset($adjList[$c])) {
            foreach ($adjList[$c] as $d) {
                $inDegree[$d]--;
                if ($inDegree[$d] == 0) {
                    $queue[] = $d;
                }
            }
        }
    }

    if (count($output) < count($inDegree)) {
        return "";
    }

    return implode("", $output);
}

Ставь 👍 и забирай 📚 Базу знаний