leetcode/alien-dictionary.py at master · cannium/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def uniqs(words):
    uniq = {}
    for w in words:
        for c in w:
            uniq[c] = 1
    return uniq.keys()

def index(c):
    return ord(c) - ord('a')

def char(i):
    return chr(i+97)

def dfs(visitedInRecursion, now, d, visitedChar, stack):
    visitedChar[now] = 1
    for i in range(26):
        if now != i and d[now][i] == 1:
            if i in visitedInRecursion and visitedInRecursion[i] == 1:
                return True
            if visitedChar[i] == 1:
                continue
            visitedInRecursion[i] = 1
            circle = dfs(visitedInRecursion, i, d, visitedChar, stack)
            if circle:
                return True
            visitedInRecursion[i] = 0
    stack.append(now)
    return False

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

        uniq = uniqs(words)
        if len(words) == 1:
            return ''.join(uniq)

        d = [[0 for i in range(26)] for j in range(26)]
        for i in range(len(words) - 1):
            a = words[i]
            b = words[i+1]
            for j in range(min(len(a), len(b))):
                if a[j] != b[j]:
                    d[index(a[j])][index(b[j])] = 1
                    break
        visitedChar = [0] * 26
        stack = []
        for c in uniq:
            ic = index(c)
            if visitedChar[ic] == 1:
                continue
            visitedInRecursion = {ic: 1}
            circle = dfs(visitedInRecursion, ic, d, visitedChar, stack)
            if circle:
                return ''

        return ''.join(char(x) for x in stack[::-1])