Topological Sort


  • 0

    Be careful when

    1. an invalid input is given,that is 'a' both before 'b' and after 'b'
    2. 'abcd' is before 'abc'
    class Solution(object):
        def alienOrder(self, words):
            pre, suc = collections.defaultdict(set), collections.defaultdict(set)
            allchr = set()
            for i in xrange(len(words)):
                for j in xrange(i + 1, len(words)):
                    for idx in xrange(min(len(words[i]), len(words[j]))):
                        if words[i][idx] != words[j][idx]:
                            if words[i][idx] in suc[words[j][idx]]:
                                return ''
                            pre[words[j][idx]].add(words[i][idx])
                            suc[words[i][idx]].add(words[j][idx])
                            break
                    if words[i].startswith(words[j]) and len(words[i]) > len(words[j]):
                        return ''
            for w in words:
                for c in w:
                    allchr.add(c)
            ans = ''
            q = allchr - set(pre.keys())
    
            while q:
                f = q.pop()
                ans = ans + f
                lst = suc[f]
                for l in lst:
                    pre[l].remove(f)
                    if not pre[l]:
                        q.add(l)
                        del pre[l]
            return ans
    
    

Log in to reply
 

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