Alien Dictionary

此题的迷惑性非常之强，首先对题目意思的理解就是一个很大的问题，这里面的字母排序到底是怎么排序的，再就发现实际上每两个词之间，我们所能确定的顺序只有一对，也就是他们公共前缀后的第一个不同字母这一对（也可能根本没有这一对的存在），其次，如果用BFS来做，出入度的判断什么都好说，还有最后的用队列BFS都是正常流程，但是这里有几个大坑，哈希表里面存结点的child应该用set而不是list，两个词长度不一样，我们找到那对大小关系之后，还必须把两个词里面所有出现的字母全部加入一个专门记录出现了多少字母的set里面去，而这两个步骤很难在一起做，另外记录入度的数组ind有可能碰到两次一样的大小关系，比如出现了两次a在b前的情况，我们只能记录一次，记录两次则产生错误结果，最后找到第一个不同字母之后循环要break而不能再继续找下去了，总之BFS做这道题比较坑，陷阱多，另外还要注意单个词和没有词的情况

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """        
        n = len(words)
        if not n:
            return ''
        if n == 1:
            return words[0]

        store = collections.defaultdict(set)
        ind = [0] * 26
        charList = set()
        for i in xrange(n - 1):
            wordA, wordB = words[i], words[i + 1]
            charList |= set(wordA)
            charList |= set(wordB)
            for i in xrange(min(len(wordA), len(wordB))):
                if wordA[i] != wordB[i]:
                    if wordB[i] not in store[wordA[i]]:
                        store[wordA[i]].add(wordB[i])
                        ind[ord(wordB[i]) - ord('a')] += 1
                    break

        queue = collections.deque([x for x in charList if ind[ord(x) - ord('a')] == 0])

        result = ''
        while queue:
            char = queue.pop()
            result += char
            for child in store[char]:
                ind[ord(child) - ord('a')] -= 1
                if ind[ord(child) - ord('a')] == 0:
                    queue.appendleft(child)

        return result if len(result) == len(charList) else ''