269. Alien Dictionary

• Time: $O(26 + n)$
• Space: $O(26 + n)$

C++JavaPython

class Solution {
 public:
  string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    vector<int> inDegrees(26);
    buildGraph(graph, words, inDegrees);
    return topology(graph, inDegrees);
  }

 private:
  void buildGraph(unordered_map<char, unordered_set<char>>& graph,
                  const vector<string>& words, vector<int>& inDegrees) {
    // Create a node for each character in each word.
    for (const string& word : words)
      for (const char c : word)
        if (!graph.contains(c))
          graph[c] = unordered_set<char>();

    for (int i = 1; i < words.size(); ++i) {
      const string& first = words[i - 1];
      const string& second = words[i];
      const int length = min(first.length(), second.length());
      for (int j = 0; j < length; ++j) {
        const char u = first[j];
        const char v = second[j];
        if (u != v) {
          if (!graph[u].contains(v)) {
            graph[u].insert(v);
            ++inDegrees[v - 'a'];
          }
          break;  // The order of characters after this are meaningless.
        }
        // e.g. first = "ab", second = "a" -> invalid
        if (j == length - 1 && first.length() > second.length()) {
          graph.clear();
          return;
        }
      }
    }
  }

  string topology(unordered_map<char, unordered_set<char>>& graph,
                  vector<int>& inDegrees) {
    string s;
    queue<char> q;

    for (const auto& [c, _] : graph)
      if (inDegrees[c - 'a'] == 0)
        q.push(c);

    while (!q.empty()) {
      const char u = q.front();
      q.pop();
      s += u;
      for (const char v : graph[u])
        if (--inDegrees[v - 'a'] == 0)
          q.push(v);
    }

    // e.g. words = ["z", "x", "y", "x"]
    return s.length() == graph.size() ? s : "";
  }
};

class Solution {
  public String alienOrder(String[] words) {
    Map<Character, Set<Character>> graph = new HashMap<>();
    int[] inDegrees = new int[26];
    buildGraph(graph, words, inDegrees);
    return topology(graph, inDegrees);
  }

  private void buildGraph(Map<Character, Set<Character>> graph, String[] words, int[] inDegrees) {
    // Create a node for each character in each word.
    for (final String word : words)
      for (final char c : word.toCharArray())
        graph.putIfAbsent(c, new HashSet<>());

    for (int i = 1; i < words.length; ++i) {
      final String first = words[i - 1];
      final String second = words[i];
      final int length = Math.min(first.length(), second.length());
      for (int j = 0; j < length; ++j) {
        final char u = first.charAt(j);
        final char v = second.charAt(j);
        if (u != v) {
          if (!graph.get(u).contains(v)) {
            graph.get(u).add(v);
            ++inDegrees[v - 'a'];
          }
          break; // The order of characters after this are meaningless.
        }
        // e.g. first = "ab", second = "a" -> invalid
        if (j == length - 1 && first.length() > second.length()) {
          graph.clear();
          return;
        }
      }
    }
  }

  private String topology(Map<Character, Set<Character>> graph, int[] inDegrees) {
    StringBuilder sb = new StringBuilder();
    Queue<Character> q = graph.keySet()
                             .stream()
                             .filter(c -> inDegrees[c - 'a'] == 0)
                             .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      final char u = q.poll();
      sb.append(u);
      for (final char v : graph.get(u))
        if (--inDegrees[v - 'a'] == 0)
          q.offer(v);
    }

    // e.g. words = ["z", "x", "y", "x"]
    return sb.length() == graph.size() ? sb.toString() : "";
  }
}

class Solution:
  def alienOrder(self, words: list[str]) -> str:
    graph = {}
    inDegrees = [0] * 26

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

  def _buildGraph(
      self,
      graph: dict[str, set[str]],
      words: list[str],
      inDegrees: list[int],
  ) -> None:
    # Create a node for each character in each word.
    for word in words:
      for c in word:
        if c not in graph:
          graph[c] = set()

    for first, second in zip(words, words[1:]):
      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)
            inDegrees[string.ascii_lowercase.index(v)] += 1
          break  # The order of characters after this are meaningless.
        # First = 'ab', second = 'a' . invalid
        if j == length - 1 and len(first) > len(second):
          graph.clear()
          return

  def _topology(self, graph: dict[str, set[str]], inDegrees: list[int]) -> str:
    s = ''
    q = collections.deque()

    for c in graph:
      if inDegrees[string.ascii_lowercase.index(c)] == 0:
        q.append(c)

    while q:
      u = q.pop()
      s += u
      for v in graph[u]:
        inDegrees[string.ascii_lowercase.index(v)] -= 1
        if inDegrees[string.ascii_lowercase.index(v)] == 0:
          q.append(v)

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