LeetCode-Solutions/Python/alien-dictionary.py at master · pythonpeixun/LeetCode-Solutions · GitHub

History

112 lines (94 loc) · 3.43 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

# Time: O(n)

# Space: O(|V|+|E|) = O(26 + 26^2) = O(1)

import collections

# BFS solution.

class Solution(object):

def alienOrder(self, words):

"""

:type words: List[str]

:rtype: str

"""

result, in_degree, out_degree = [], {}, {}

zero_in_degree_queue = collections.deque()

nodes = set()

for word in words:

for c in word:

nodes.add(c)

for i in xrange(1, len(words)):

if (len(words[i-1]) > len(words[i]) and

words[i-1][:len(words[i])] == words[i]):

return ""

self.findEdges(words[i - 1], words[i], in_degree, out_degree)

for node in nodes:

if node not in in_degree:

zero_in_degree_queue.append(node)

while zero_in_degree_queue:

precedence = zero_in_degree_queue.popleft()

result.append(precedence)

if precedence in out_degree:

for c in out_degree[precedence]:

in_degree[c].discard(precedence)

if not in_degree[c]:

zero_in_degree_queue.append(c)

del out_degree[precedence]

if out_degree:

return ""

return "".join(result)

# Construct the graph.

def findEdges(self, word1, word2, in_degree, out_degree):

str_len = min(len(word1), len(word2))

for i in xrange(str_len):

if word1[i] != word2[i]:

if word2[i] not in in_degree:

in_degree[word2[i]] = set()

if word1[i] not in out_degree:

out_degree[word1[i]] = set()

in_degree[word2[i]].add(word1[i])

out_degree[word1[i]].add(word2[i])

break

# DFS solution.

class Solution2(object):

def alienOrder(self, words):

"""

:type words: List[str]

:rtype: str

"""

# Find ancestors of each node by DFS.

nodes, ancestors = set(), {}

for i in xrange(len(words)):

for c in words[i]:

nodes.add(c)

for node in nodes:

ancestors[node] = []

for i in xrange(1, len(words)):

if (len(words[i-1]) > len(words[i]) and

words[i-1][:len(words[i])] == words[i]):

return ""

self.findEdges(words[i - 1], words[i], ancestors)

# Output topological order by DFS.

result = []

visited = {}

for node in nodes:

if self.topSortDFS(node, node, ancestors, visited, result):

return ""

return "".join(result)

# Construct the graph.

def findEdges(self, word1, word2, ancestors):

min_len = min(len(word1), len(word2))

for i in xrange(min_len):

if word1[i] != word2[i]:

ancestors[word2[i]].append(word1[i])

break

# Topological sort, return whether there is a cycle.

def topSortDFS(self, root, node, ancestors, visited, result):

if node not in visited:

visited[node] = root

for ancestor in ancestors[node]:

if self.topSortDFS(root, ancestor, ancestors, visited, result):

return True

result.append(node)

elif visited[node] == root:

# Visited from the same root in the DFS path.

# So it is cyclic.

return True

return False

LeetCode-Solutions/Python/alien-dictionary.py at master · pythonpeixun/LeetCode-Solutions · GitHub

Expand file tree

Breadcrumbs

alien-dictionary.py

Latest commit

History

Breadcrumbs

alien-dictionary.py

File metadata and controls