269. Alien dictionary

solve.py

def solve(words):
    def build_graph(words, indegree, adj):
        # initialize map with all possible nodes
        for x in range(len(words)):
            for y in range(len(words[x])):
                if y not in adj:
                    adj[words[x][y]] = set()

        for i in range(1, len(words)):
            first = words[i-1]
            second = words[i]
            size = min(len(first), len(second))

            for j in range(size):
                if first[j] != second[j]:
                    _in, _out = second[j], first[j]

                    if _in not in adj[_out]:
                        # keeps chars, indegree keeps integers
                        adj[_out].add(_in)
                        indegree[ord(_in) - ord('a')] += 1
                        break
        
    def topsort(adj, indegree):
        nodes = []
        for c in adj:
            if indegree[ord(c) - ord('a')] == 0:
                nodes.append(c)

        ans = ''
        while nodes:
            curr = nodes.pop()
            ans += curr
            
            for n in adj[curr]:
                indegree[ord(n) - ord('a')] -= 1

                if indegree[ord(n) - ord('a')] == 0:
                    nodes.append(n)
        
        return ans if len(ans) == len(adj) else ''

    indegree = [0] * 26
    adj = {}
    build_graph(words, indegree, adj)
    return topsort(adj, indegree)


words = [
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
# words = ['z', 'x']
print(solve(words))