[算法] Alien Dictionary

Question
Alien Dictionary

Question Description

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.

notice

1. You may assume all letters are in lowercase.
2. The dictionary is invalid, if a is prefix of b and b is appear before a.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return the smallest in normal lexicographical order

Language
Python 3

Thinking Solution
(1) Build it as graph (Find the relation of current and next string)
(2) Find indegree.
(3) Perform BFS

Data structure description
""" Definition for a Directed graph node class DirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = [] """



Solution
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.topo_sort(graph) def build_graph(self, words): graph = {} # init for word in words: for c in word: if c not in graph: graph[c] = set() # add 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]: graph[words[i][j]].add(words[i+1][j]) break return graph def topo_sort(self, graph): indegree = {node: 0 for node in graph} # update for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 order = '' queue = [n for n in graph if indegree[n] == 0] heapify(queue) while queue: curr_node = heappop(queue) order += curr_node for neighbor in graph[curr_node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: heappush(queue, neighbor) if len(order) == len(graph): return order return ''

Reference Link
https://www.lintcode.com/problem/alien-dictionary/description