Alien Dictionary

code:

 from collections import defaultdict

class Solution:

    def __init__(self):

        self.graph=defaultdict(list)

        

        

    def addEdge(self,u,v):

        self.graph[u].append(v)

        

    

    def topUtil(self,visited,i,stack):

        visited[i]=True

        

        for k in self.graph[i]:

            if visited[k]==False:

                self.topUtil(visited,k,stack)

        

        stack.append(i)    

        

        

        

    def findOrder(self,dict, N, k):

        

        for i in range(len(dict)-1):

            w1=dict[i]

            w2=dict[i+1]

            

            for j in range( min(len(w1),len(w2)) ):

                if w1[j]!=w2[j]:

                    #print(w1[j],w2[j])

                    self.addEdge(ord(w1[j])-97,ord(w2[j])-97)

                    break

                    

        #print(self.graph)

                

                    

    # top(self,k):

        visited=[False]*k

        stack=[]

        for i in range(k):

            if visited[i]==False:

                self.topUtil(visited,i,stack)

                

        ans=[]        

        while stack:

            ans.append(stack.pop())

        

        for l in range(len(ans)):

            

            ans[l]=chr(ans[l]+97)

            

        print(ans)

        

        

N = 5

K = 4

dict = ["baa","abcd","abca","cab","cad"]

g=Solution()       

g.findOrder(dict,N,K)