My Python DFS + topsort with comments


  • 0

    Idea is trivial. Just build a graph using first different char in two consecutive word. Then do a DFS with topological sort. Last, combine sorted list and chars which are not in the graph but in words lists into a string.

    class Solution(object):
    def dfsHelper(self, v, color, graph, res, letterPos):
        color[v] = 1
        adj = graph[v]
        for letter in adj:
            w = letterPos(letter)
            if color[w] == 0 :
                if self.dfsHelper(w, color, graph, res, letterPos) == False:
                    return False
            elif color[w] == 1:
                # circle detection to judge the case ["z", "a", "z"]
                return False
        color[v] = 2
        res.append(chr(v + ord('a')))
        return True
            
    def alienOrder(self, words):
        letterPos = lambda x: ord(x) - ord('a')
        if words is None or len(words) == 0:
            return ""
        res, resUnused, graph, color = [], [], [[] for _ in range(26)], [0 for _ in range(26)]
        if len(words) == 1:
            return words[0]
        
        for i in xrange(1, len(words)):
            pos = 0
            # find first different char
            while pos < len(words[i - 1]) and pos < len(words[i]):
                if words[i - 1][pos] == words[i][pos]:
                    pos += 1
                    if pos >= min(len(words[i - 1]), len(words[i])):
                        pos = 0
                        break
                else:
                    break
            if words[i - 1][pos] != words[i][pos]:
                graph[letterPos(words[i - 1][pos])].append(words[i][pos])
    
        for i in xrange(0, 26):
            if graph[i] and color[i] == 0:
                if self.dfsHelper(i, color, graph, res, letterPos) == False:
                    # use return value to quit ealier after it detects circle
                    return ""
        
        # collect all unsorted chars
        for i in xrange(0, len(words)):
            for j in xrange(0, len(words[i])):
                if color[letterPos(words[i][j])] == 0:
                    resUnused.append(words[i][j])
                    color[letterPos(words[i][j])] = 1
        
        return "".join(res)[::-1] + "".join(resUnused)

Log in to reply
 

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