Python DFS with topological sort


  • 0
    A
    def alienOrder(self, words):
        self.Map = {c: [] for word in words for c in word}
        for word1, word2 in zip(words[:-1], words[1:]):
            for i in xrange(min(len(word1), len(word2))):
                if word1[i] != word2[i]:
                    self.Map[word1[i]].append(word2[i])
                    break
    
        self.visit = {}
        self.circle = False
        self.ans = ''
        for k in self.Map:
            if self.circle:
                break
            if k not in self.visit:
                self.dfs(k)
        
        if self.circle:
            return ''
        return self.ans[::-1] # reverse
    
    def dfs(self, k):
        if self.circle:
            return
        
        if k in self.visit:
            if self.visit[k] == 1:
                self.circle = True
            return
        
        self.visit[k] = 1
        for niegh in self.Map[k]:
            self.dfs(niegh)
        self.ans += k
        self.visit[k] = 2

Log in to reply
 

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