Задача: 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 становится нулевым.
Продолжать до тех пор, пока очередь не станет пустой.
Проверить наличие циклов и вернуть результат.

😎 Решение:

import Foundation

class Solution {
    func alienOrder(_ words: [String]) -> String {
        var adjList = [Character: Set<Character>]()
        var inDegree = [Character: Int]()
        
        for word in words {
            for char in word {
                inDegree[char] = 0
            }
        }
        
        for (firstWord, secondWord) in zip(words, words.dropFirst()) {
            for (c, d) in zip(firstWord, secondWord) {
                if c != d {
                    if !adjList[c, default: []].contains(d) {
                        adjList[c, default: []].insert(d)
                        inDegree[d, default: 0] += 1
                    }
                    break
                }
            }
            if secondWord.count < firstWord.count && firstWord.hasPrefix(secondWord) {
                return ""
            }
        }
        
        var output = [Character]()
        var queue = [Character]()
        
        for (char, degree) in inDegree where degree == 0 {
            queue.append(char)
        }
        
        while !queue.isEmpty {
            let c = queue.removeFirst()
            output.append(c)
            for d in adjList[c] ?? [] {
                inDegree[d]! -= 1
                if inDegree[d] == 0 {
                    queue.append(d)
                }
            }
        }
        
        if output.count < inDegree.count {
            return ""
        }
        
        return String(output)
    }
}

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