Python DFS Solution


  • 0
    L

    Feedback for improvement is appreciated!

    class Node(object):
        def __init__(self, value):
            self.value = value
            self.visited = False
            self.onPath = False
            self.adjacent_nodes = []
    
        def point_to(self, node):
            return node in self.adjacent_nodes
    
    
    class CyclicGraphException(Exception):
        pass
    
    
    class AlienOrder(object):
        def alienOrder(self, words):
            try:
                graph = self.form_graph(words)
                sort = self.topological_sort(graph)
            except CyclicGraphException:
                return ""
            return "".join(sort)
    
        def form_graph(self, words):
            graph = {}
            for word in words:
                for char in word:
                    if char not in list(graph):
                        graph[char] = Node(char)
            for i in range(len(words) - 1):
                    word1 = words[i]
                    word2 = words[i + 1]
                    for k in range(min(len(word1), len(word2))):
                        if word1[k] == word2[k]:
                            k += 1
                        else:
                            if graph[word2[k]].point_to(graph[word1[k]]):
                                raise CyclicGraphException()
                            if graph[word2[k]] not in graph[word1[k]].adjacent_nodes:
                                graph[word1[k]].adjacent_nodes.append(graph[word2[k]])
                            break
            return graph
    
        def topological_sort(self, graph):
            stack = []
            for node in graph.values():
                if not node.visited:
                    self.dfs(stack, node)
            return stack[::-1]
    
        def dfs(self, stack, node):
            node.onPath = True
            for next_node in node.adjacent_nodes:
                if next_node.onPath:
                    raise CyclicGraphException()
                if not next_node.visited:
                    self.dfs(stack, next_node)
            stack.append(node.value)
            node.visited = True
            node.onPath = False
    
    
    if __name__ == "__main__":
            words_1 = ["wrt", "wrf", "er", "ett", "rftt"]
            expected_order_1 = "wertf"
    
            words_2 = ["z", "x"]
            expected_order_2 = "zx"
    
            words_3 = ["z", "x", "z"]
            expected_order_3 = ""
    
            words_4 = ["a", "b", "c", "a"]
            expected_order_4 = ""
    
            assert(expected_order_1 == AlienOrder().alienOrder(words_1))
            assert(expected_order_2 == AlienOrder().alienOrder(words_2))
            assert(expected_order_3 == AlienOrder().alienOrder(words_3))
            assert(expected_order_4 == AlienOrder().alienOrder(words_4))
    

  • 0
    L

    Solution of count node inbound:

    from collections import deque
    
    class Node(object):
        def __init__(self, value):
            self.value = value
            self.visited = False
            self.onPath = False
            self.inbound = 0
            self.outbound = 0
            self.adjacent_nodes = []
    
        def point_to(self, node):
            return node in self.adjacent_nodes
    
    
    class CyclicGraphException(Exception):
        pass
    
    class Solution(object):
        class CyclicGraphException(Exception):
            pass
        
        def alienOrder(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            try:
                graph = self.form_graph(words)
                sort = self.topological_sort(graph)
            except CyclicGraphException:
                return ""
            return "".join(sort)
    
        def form_graph(self, words):
            graph = {}
            for word in words:
                for char in word:
                    if char not in list(graph):
                        graph[char] = Node(char)
            for i in range(len(words) - 1):
                    word1 = words[i]
                    word2 = words[i + 1]
                    for k in range(min(len(word1), len(word2))):
                        if word1[k] == word2[k]:
                            k += 1
                        else:
                            if graph[word2[k]].point_to(graph[word1[k]]):
                                raise CyclicGraphException()
                            if graph[word2[k]] not in graph[word1[k]].adjacent_nodes:
                                graph[word1[k]].adjacent_nodes.append(graph[word2[k]])
                                graph[word1[k]].outbound += 1
                                graph[word2[k]].inbound += 1
                            break
            return graph
    
        def topological_sort(self, graph):
            order = []
            process_next = deque([])
            for k in list(graph):
                if graph[k].inbound == 0:
                    process_next.append(graph[k])
            while process_next:
                current_node = process_next.popleft()
                order.append(current_node.value)
                for next_node in current_node.adjacent_nodes:
                    next_node.inbound -= 1
                    if next_node.inbound == 0:
                        process_next.append(next_node)
            if len(order) != len(list(graph)):
                return []
            return order
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.