Alien dictionary
July 26, 2022
graphProblem URL: Alien dictionary
We will first create an adjacency list from our input array. If 2 array has a different first charcter, then word1[0] should be arreared before word2[0]. When the grph is already created, we can then do a topological sort on the adjacency list. we will do it using DFS.
class Solution:
def alienOrder(self, words: List[str]) -> str:
graph = self.createGraph(words)
return self.topologicalSort(graph)
def topologicalSort(self, graph: List[List[str]]) -> str:
visited = set()
result = []
for node in graph:
if node not in visited:
self.dfs(node, graph, visited, result)
return "".join(result)
def dfs(self, node, graph, visited, result):
if node in visited:
return
visited.add(node)
for n in graph[node]:
self.dfs(n, graph, visited, result)
result.append(node)
def createGraph(self, words: List[str]) -> List[List[str]]:
graph = {}
for word in words:
for char in word:
graph[char] = set()
for i in range(len(words)-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
Time Complexity: O(n)
, n is the number of characters combined in the input array.
Space Complexity: O(n)