Python solution passed all new test cases (as of 11/04/2016)


  • 2
    W

    It seems that old solutions cannot handle the new test cases: ["wrtkj","wrt"], ["za","zb","ca","cb"].
    For inputs like ["wrtkj","wrt"], I add code for sanity check: if w1.startswith(w2) and len(w1) > len(w2): return ''
    For inputs like ["za","zb","ca","cb"], a is ancestor of b, use pre = collections.defaultdict(set) to count a only once.

    def alienOrder(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            neigh = collections.defaultdict(set)
            pre = collections.defaultdict(set)   
            for pair in zip(words, words[1:]):
                w1, w2 = pair
                if w1.startswith(w2) and len(w1) > len(w2):  # sanity check 
                    return ''   
                for c1, c2 in zip(*pair):
                    if c1 != c2:
                        neigh[c1].add(c2)
                        pre[c2].add(c1)
                        break
                    
            chars = set(''.join(words))
            stack = [c for c in chars if not pre[c]]   # these are heads
            res = ''
           # DFS
            while stack:
                ch = stack.pop()
                res += ch
                for nbr in neigh[ch]:
                    pre[nbr].remove(ch)
                    if not pre[nbr]:
                        stack.append(nbr)
                pre.pop(ch)
            return res if not pre else ''
    

Log in to reply
 

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