LeetCode

LeetCode 269 Alien Dictionary - Hard

269. Alien Dictionary

Jan 1, 2021·2 min read·#LeetCode #Hard #Python

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input: [ "wrt", "wrf", "er", "ett", "rftt" ]

Output: "wertf" Example 2:

Input: [ "z", "x" ]

Output: "zx" Example 3:

Input: [ "z", "x", "z" ]

Output: ""

Explanation: The order is invalid, so return "". Note:

You may assume all letters are in lowercase. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.

Solution

### Topological Sorting + Heap queue:
 
 
 
from heapq import heappush, heappop, heapify
class Solution:
    """
    @param words: a list of words
    @return: a string which is correct order
    """
    def alienOrder(self, words):
        # Write your code here
        graph = self.build_graph(words)
        return self.topological_sort(graph)
        
    def build_graph(self, words):
        # key is node, value is neighbors
        graph = {}
 
        # initialize graph
        for word in words:
            for c in word:
                if c not in graph:
                    graph[c] = set() 
 
        # add edges        
        n = len(words)
        for i in range(n - 1):
            for j in range(min(len(words[i]), len(words[i + 1]))):
                if words[i][j] != words[i + 1][j]:
                    if words[i + 1][j] not in graph[words[i][j]]:
                        graph[words[i][j]].add(words[i + 1][j])
                    break
            else:
                if len(words[i]) > len(words[i + 1]):
                    return ""
                
        return graph
 
    def topological_sort(self, graph):
        # before looking into this part of code
        # you should know how to use bfs algorithm to do topological sorting
        # if you don't know, please google it first or join us at 九章算法班.
        
        # initialize indegree 
        indegree = {
            node: 0
            for node in graph
        }
        
        # calculate indegree
        for node in graph:
            for neighbor in graph[node]:
                indegree[neighbor] = indegree[neighbor] + 1
        
        # use heapq instead of regular queue so that we can get the 
        # smallest lexicographical order
        queue = [node for node in graph if indegree[node] == 0]
        heapify(queue)
        
        # regular bfs algorithm to do topological sorting
        topo_order = ""
        while queue:
            node = heappop(queue)
            topo_order += node
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    heappush(queue, neighbor)
            
        # if all nodes popped
        if len(topo_order) == len(graph):
            return topo_order
        
        return ""

LeetCode 269 Alien Dictionary - Hard

269. Alien Dictionary — Hard

Problem

Solution

Comments