Alien Dictionary

from collections import defaultdict, deque
from typing import Dict, List, Set

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)
        inDegree = defaultdict(int)

        self._buildGraph(graph, words, inDegree)
        return self._topology(graph, inDegree)

    def _buildGraph(self, graph: Dict[str, Set[str]], words: List[str], inDegree: Dict[str, int]) -> None:
        # Create a node for each character in each word
        for word in words:
            for c in word:
                inDegree[c] = 0  # necessary for final char counting

        for first, second in zip(words, words[1:]): # or pairwise(words)
            length = min(len(first), len(second))
            for j in range(length):
                u = first[j]
                v = second[j]
                if u != v:
                    if v not in graph[u]:
                        graph[u].add(v)
                        inDegree[v] += 1
                    break  # Later characters' order is meaningless
                if j == length - 1 and len(first) > len(second):
                    # If 'ab' comes before 'a', it's an invalid order
                    graph.clear()
                    return

    def _topology(self, graph: Dict[str, Set[str]], inDegree: Dict[str, int]) -> str:
        result = ''
        q = deque([c for c in inDegree if inDegree[c] == 0])

        while q:
            u = q.popleft()
            result += u
            for v in graph[u]:
                inDegree[v] -= 1
                if inDegree[v] == 0:
                    q.append(v)

        # If there are remaining characters in inDegree, it means there's a cycle
        if any(inDegree.values()):
            return ''

        # Words = ['z', 'x', 'y', 'x']
        return result if len(result) == len(indegree) else ''

############

import collections


class Node(object):
  def __init__(self, val):
    self.val = val
    self.neighbors = []

  def connect(self, node):
    self.neighbors.append(node)

  def getNbrs(self):
    return self.neighbors


class Solution(object):
  def alienOrder(self, words):
    """
    :type words: List[str]
    :rtype: str
    """

    def dfs(root, graph, visited):
      visited[root] = 1
      for nbr in graph[root].getNbrs():
        if visited[nbr.val] == 0:
          if not dfs(nbr.val, graph, visited):
            return False
        elif visited[nbr.val] == 1:
          return False

      visited[root] = 2
      self.ans += root
      return True

    self.ans = ""
    graph = {}
    visited = collections.defaultdict(int)
    self.topNum = 0
    for i in range(0, len(words) - 1):
      a = words[i]
      b = words[i + 1]
      i = 0
      while i < len(a) and i < len(b):
        if a[i] != b[i]:
          nodeA = nodeB = None
          if a[i] not in graph:
            nodeA = Node(a[i])
            graph[a[i]] = nodeA
          else:
            nodeA = graph[a[i]]
          if b[i] not in graph:
            nodeB = Node(b[i])
            graph[b[i]] = nodeB
          else:
            nodeB = graph[b[i]]
          nodeA.connect(nodeB)
          break
        i += 1
      if i < len(a) and i >= len(b):
        return ""

    for c in graph:
      if visited[c] == 0:
        if not dfs(c, graph, visited):
          return ""

    unUsedSet = set()
    for word in words:
      for c in word:
        unUsedSet.add(c)

    for c in unUsedSet:
      if c not in graph:
        self.ans += c
    return self.ans[::-1]