269. Alien Dictionary

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public string AlienOrder(string[] words) {
        var adjList = new Dictionary<char, HashSet<char>>();
        var inDegree = new Dictionary<char, int>();
        foreach (var word in words) {
            foreach (var c in word) {
                inDegree[c] = 0;
            }
        }
        for (int i = 0; i < words.Length - 1; i++) {
            var firstWord = words[i];
            var secondWord = words[i + 1];
            for (int j =

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string AlienOrder(vector<string> words) {
        var adjList = new unordered_map<char, HashSet<char>>();
        var inDegree = new unordered_map<char, int>();
        foreach (var word in words) {
            foreach (var c in word) {
                inDegree[c] = 0;
            }
        }
        for (int i = 0; i < words.size() - 1; i++) {
            var firstWord = words[i];
            var secondWord = words[i + 1];
            for (int j =

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adjList = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String firstWord = words[i];
            String secondWord = words[i + 1];
            for (int j = 0; j < Math.min(firstWord.length(), secondWord.length()); j++) {
                char c = firstWord.charAt(j);
                char d = secondWord.charAt(j);
                if (c != d) {
                    if (!adjList.containsKey(c)) {
                        adjList.put(c, new HashSet<>());
                    }
                    if (adjList.get(c).add(d)) {
                        inDegree.put(d, inDegree.get(d) + 1);
                    }
                    break;
                }
            }
            if (secondWord.length() < firstWord.length() && firstWord.startsWith(secondWord)) {
                return "";
            }
        }

        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        StringBuilder output = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            output.append(c);
            if (adjList.containsKey(c)) {
                for (char d : adjList.get(c)) {
                    inDegree.put(d, inDegree.get(d) - 1);
                    if (inDegree.get(d) == 0) {
                        queue.add(d);
                    }
                }
            }
        }

        if (output.length() < inDegree.size()) {
            return "";
        }

        return output.toString();
    }
}

var alienOrder = function(words) {
    const adjList = new Map();
    const inDegree = new Map();
    
    for (const word of words) {
        for (const char of word) {
            inDegree.set(char, 0);
        }
    }
    
    for (let i = 0; i < words.length - 1; i++) {
        const firstWord = words[i];
        const secondWord = words[i + 1];
        for (let j = 0; j < Math.min(firstWord.length, secondWord.length); j++) {
            const c = firstWord[j];
            const d = secondWord[j];
            if (c !== d) {
                if (!adjList.has(c)) {
                    adjList.set(c, new Set());
                }
                if (!adjList.get(c).has(d)) {
                    adjList.get(c).add(d);
                    inDegree.set(d, inDegree.get(d) + 1);
                }
                break;
            }
        }
        if (secondWord.length < firstWord.length && firstWord.startsWith(secondWord)) {
            return "";
        }
    }
    
    const output = [];
    const queue = [];
    
    for (const [char, degree] of inDegree.entries()) {
        if (degree === 0) {
            queue.push(char);
        }
    }
    
    while (queue.length > 0) {
        const c = queue.shift();
        output.push(c);
        if (adjList.has(c)) {
            for (const d of adjList.get(c)) {
                inDegree.set(d, inDegree.get(d) - 1);
                if (inDegree.get(d) === 0) {
                    queue.push(d);
                }
            }
        }
    }
    
    if (output.length < inDegree.size) {
        return "";
    }
    
    return output.join("");
};

from collections import defaultdict, Counter, deque

def alienOrder(self, words: List[str]) -> str:
    adj_list = defaultdict(set)
    in_degree = Counter({c: 0 for word in words for c in word})
            
    for first_word, second_word in zip(words, words[1:]):
        for c, d in zip(first_word, second_word):
            if c != d:
                if d not in adj_list[c]:
                    adj_list[c].add(d)
                    in_degree[d] += 1
                break
        else:
            if len(second_word) < len(first_word):
                return ""
    
    output = []
    queue = deque([c for c in in_degree if in_degree[c] == 0])
    while queue:
        c = queue.popleft()
        output.append(c)
        for d in adj_list[c]:
            in_degree[d] -= 1
            if in_degree[d] == 0:
                queue.append(d)
                
    if len(output) < len(in_degree):
        return ""
    
    return "".join(output)

package main

import (
    "container/list"
    "strings"
)

func alienOrder(words []string) string {
    adjList := make(map[byte]map[byte]struct{})
    inDegree := make(map[byte]int)

    for _, word := range words {
        for i := 0; i < len(word); i++ {
            inDegree[word[i]] = 0
        }
    }

    for i := 0; i < len(words)-1; i++ {
        firstWord := words[i]
        secondWord := words[i+1]
        for j := 0; j < len(firstWord) && j < len(secondWord); j++ {
            c := firstWord[j]
            d := secondWord[j]
            if c != d {
                if _, exists := adjList[c]; !exists {
                    adjList[c] = make(map[byte]struct{})
                }
                if _, exists := adjList[c][d]; !exists {
                    adjList[c][d] = struct{}{}
                    inDegree[d]++
                }
                break
            }
        }
        if len(secondWord) < len(firstWord) && strings.HasPrefix(firstWord, secondWord) {
            return ""
        }
    }

    queue := list.New()
    for char, degree := range inDegree {
        if degree == 0 {
            queue.PushBack(char)
        }
    }

    var output strings.Builder
    for queue.Len() > 0 {
        elem := queue.Front()
        c := elem.Value.(byte)
        queue.Remove(elem)
        output.WriteByte(c)
        if neighbors, exists := adjList[c]; exists {
            for d := range neighbors {
                inDegree[d]--
                if inDegree[d] == 0 {
                    queue.PushBack(d)
                }
            }
        }
    }

    if output.Len() < len(inDegree) {
        return ""
    }

    return output.String()
}

Algorithm

1️⃣

Извлечение отношений порядка и создание списков смежности:

Извлечь отношения порядка между буквами из слов.

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

2️⃣

Подсчет числа Entréeящих ребер:

Подсчитать количество Entréeящих ребер (in-degree) для каждой буквы.

Построить исходящий список смежности и одновременно считать Entréeящие ребра для каждой буквы.

3️⃣

Обход в ширину (BFS):

Инициализировать очередь буквами с нулевым in-degree.

Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым.

Продолжать до тех пор, пока очередь не станет пустой.

Проверить наличие циклов и вернуть результат.

😎