LeetCode #269: Alien Dictionary

LeetCode Solutions

https://leetcode.com/problems/alien-dictionary/description/

To solve the problem, we need to consider the given list of words and construct a graph of the characters and their dependencies. Each edge in the graph represents the order of characters. Then, we can perform a topological sort on the graph to obtain the sorted order.

Steps:

  1. Create an empty graph with a hash table where each character points to an empty set.
  2. Iterate over the given list of words and compare each adjacent pair of words. For each pair of characters at the same index, if they are different, add an edge to the graph from the first character to the second character.
  3. Perform topological sort on the graph using Kahn’s algorithm: a. Create an empty queue and a hash table to keep track of in-degree of each node. b. Initialize the hash table with 0 in-degree for all nodes. c. Iterate over the graph to update the in-degree of each node. d. Enqueue all nodes with 0 in-degree into the queue. e. While the queue is not empty, dequeue a node, add it to the sorted order and decrement the in-degree of its neighbors. If the in-degree of any neighbor becomes 0, add it to the queue.
  4. If the length of the sorted order is equal to the number of nodes in the graph, return the sorted order as the lexicographically smallest order. Otherwise, return an empty string.

Here is the solution in python3:

from collections import deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = {c: set() for word in words for c in word}
        in_degree = {c: 0 for c in graph}

        for i in range(1, len(words)):
            word1, word2 = words[i-1], words[i]
            if len(word1) > len(word2) and word1.startswith(word2):
                return ""
            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    if word2[j] not in graph[word1[j]]:
                        graph[word1[j]].add(word2[j])
                        in_degree[word2[j]] += 1
                    break

        q = deque([c for c in in_degree if in_degree[c] == 0])
        res = ""
        while q:
            curr = q.popleft()
            res += curr
            for neighbor in graph[curr]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    q.append(neighbor)

        return res if len(res) == len(graph) else ""

Time Complexity

Creating the graph takes O(N), where N is the total number of characters in all words. Performing topological sort takes O(V+E), where V is the number of nodes in the graph and E is the number of edges in the graph. Since we build the graph based on the words, the number of edges can be at most O(N), so the total time complexity is O(N+V+E) = O(N).

Space Complexity

Creating the graph takes O(N) space. In-degree hash table takes O(V) space. Queue takes O(V) space. The total space complexity is O(N+V).