Alien Dictionary - Leetcode Solution

Problem description:

There is a new alien language that uses the English alphabet, but the order of the letters is unknown to you. You are given a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of the alphabet from the dictionary.

Solution:

The given problem can be solved using Topological Sort of Graph. We can consider each character of the word as a vertex. For each pair of words, if the corresponding characters at the same position are different, we can connect an edge from the character of the first word to the character of the second word. We can create a directed graph where each vertex represents a character, and the edge represents the order of the character.

Next, we can perform a Topological Sort of the vertices of the graph to compute the order of the alphabet. Topological Sort is an algorithm that takes a directed acyclic graph (DAG) as input and returns a linear ordering of its vertices. The linear ordering is such that for every directed edge (u, v) from vertex u to vertex v, u comes before v in the ordering.

Algorithm:

1. Create a directed graph for the characters in the input dictionary words.
2. Perform Topological Sort on the graph to get the order of characters.
3. Return the order of characters as the alphabet order.

Code:

Let’s try to implement the above algorithm in Python:

from collections import defaultdict, deque class Solution: def alienOrder(self, words: List[str]) -> str: # Create directed graph of characters graph = defaultdict(set) indegree = defaultdict(int) for i in range(len(words)-1): word1, word2 = words[i], words[i+1] for j in range(min(len(word1), len(word2))): if word1[j] == word2[j]: continue if word2[j] not in graph[word1[j]]: graph[word1[j]].add(word2[j]) indegree[word2[j]] += 1 break else: if len(word1) > len(word2): return "" # Perform Topological Sort order = [] queue = deque([c for c in indegree if indegree[c] == 0]) while queue: curr = queue.popleft() order.append(curr) for neighbor in graph[curr]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) if len(order) == len(indegree): return "".join(order) return ""

Time Complexity: O(N), where N is the total number of characters in all words. Space Complexity: O(26) = O(1), as the input contains only lowercase letters of English alphabet.

Example:

Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"

1