Python DFS, BFS, toposort solutions


  • 5
    G

    DFS:

        import collections
        
        self.greater = collections.defaultdict(set)
        
        for i in range(len(words)-1):
            minlen = min(len(words[i]), len(words[i+1]))
            j=0
            while j < minlen and words[i][j] == words[i+1][j]:
                j+=1
            if j < minlen:
                self.greater[words[i][j]].add(words[i+1][j])
                
        charset = set(''.join(words))
        
        self.mark = {}
        
        self.orderlist = collections.deque()
        
        for i in charset:
            if i not in self.mark:
                if not self.visit(i):
                    return ""
        
        return "".join(self.orderlist)
            
    def visit(self, i):
        
        if i in self.mark and self.mark[i] == 2:
            return False
        elif i in self.mark and self.mark[i] == 1:
            return True
        
        if i not in self.mark:
            self.mark[i] = 2
            
            for j in self.greater[i]:
                if not self.visit(j):
                    return False
                
            self.mark[i] = 1
            
            self.orderlist.appendleft(i)
            
            return True
    

    BFS:

        import collections
        
        que = collections.deque()
        
        less = collections.defaultdict(set)            
        greater = collections.defaultdict(set)
        
        for i in range(len(words)-1):
            minlen = min(len(words[i]), len(words[i+1]))
            j=0
            while j < minlen and words[i][j] == words[i+1][j]:
                j+=1
            if j < minlen:
                less[words[i][j]].add(words[i+1][j])
                greater[words[i+1][j]].add(words[i][j])
                que.append([words[i][j],words[i+1][j]])
                
        charset = set(''.join(words))
        
        subset = [x for x in charset if x not in greater]
        
        while que:
            [k,l] = que.popleft()
            if l in less:
                for m in less[l]:
                    if m == k:
                        return ""
                    elif k not in greater[m]:
                        greater[m].add(k)
                        que.append([k,m])
                        
        return ''.join(subset)+''.join(w[0] for w in sorted(greater.items(), key=lambda x: len(x[1])))
    

    Toposort:

        import collections
        
        less = collections.defaultdict(set)            
        greater = collections.defaultdict(set)
        
        for i in range(len(words)-1):
            minlen = min(len(words[i]), len(words[i+1]))
            j=0
            while j < minlen and words[i][j] == words[i+1][j]:
                j+=1
            if j < minlen:
                less[words[i][j]].add(words[i+1][j])
                greater[words[i+1][j]].add(words[i][j])
                
        charset = set(''.join(words))
        
        orderlist = []
        
        deque = collections.deque([x for x in charset if x not in greater])
        
        while deque:
            i = deque.popleft()
            if i in less:
                for j in less[i]:
                    greater[j].remove(i)
                    if len(greater[j]) == 0:
                        del greater[j]
                        deque.append(j)
            orderlist.append(i)
            
        if len(greater) > 0:
            return ""
        else:
            return "".join(orderlist)

Log in to reply
 

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