Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.

Example 1:

Input: 
N = 5, K = 4
dict = {"baa","abcd","abca","cab","cad"}
Output:
1
Explanation:
Here order of characters is
'b', 'd', 'a', 'c' Note that words are sorted
and in the given language "baa" comes before
"abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Example 2:

Input: 
N = 3, K = 3
dict = {"caa","aaa","aab"}
Output:
1
Explanation:
Here order of characters is
'c', 'a', 'b' Note that words are sorted
and in the given language "caa" comes before
"aaa", therefore 'c' is before 'a' in output.
Similarly we can find other orders.

Your Task:
You don’t need to read or print anything. Your task is to complete the function findOrder() which takes the string array dict[], its size N and the integer K as input parameter and returns a string denoting the order of characters in the alien language.

Expected Time Complexity: O(N + K)
Expected Space Compelxity: O(K)

Constraints:
1 ≤ N, M ≤ 300
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50

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


class Node():
def __init__(self,data):
self.data = data
self.head = None
self.next = None
class LinkedList():
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def listprint(self):
temp = self.head
arr=[]
while temp is not None:
arr.append(temp.data)
temp = temp.next
return (arr)
def insert(self,new_data):
while self.is_exists(new_data) == 'no':
temp = self.head
if temp == None:
self.head = Node(new_data)
return
while (temp):
if temp.next == None:
temp.next = Node(new_data)
return
temp = temp.next
else:
self.head = Node(new_data)
def is_exists(self,data):
temp = self.head
while temp:
if temp.data == data:
return 'yes'
temp = temp.next
return 'no'
def insert_before(self,data,new_data):
temp = self.head
new_data = Node(new_data)
if temp == None:
self.head = new_data
while temp:
if temp.data == data:
new_data.next = self.head
self.head = new_data
return
else:
while temp.next:
if temp.next.data == data:
new_data.next = temp.next
temp.next = new_data
return
temp = temp.next
return
return
def insert_after(self,data,new_data):
temp = self.head
new_data = Node(new_data)
if temp == None:
self.head = new_data
while temp:
if temp.data == data:
new_data.next = temp.next
temp.next = new_data
return
temp = temp.next
r = LinkedList()
for x in dict:
r.insert(x[0])
for i in range(len(dict)-1):
#print(dict[i],dict[i+1])
try:
for j in range(len(min(dict[i], dict[i + 1]))):
#print(dict[i][j], dict[i + 1][j])
if dict[i][j] == dict[i + 1][j] and r.is_exists(dict[i][j]) == 'no':
r.insert(dict[i][j])
elif dict[i][j] == dict[i + 1][j] and r.is_exists(dict[i][j]) == 'yes':
pass
elif dict[i][j] != dict[i + 1][j]:
if (r.is_exists(dict[i][j]) == 'no' or r.is_exists(dict[i + 1][j]) == 'no'):
if r.is_exists(dict[i][j]) == 'yes':
r.insert_after(dict[i][j], dict[i + 1][j])
elif r.is_exists(dict[i + 1][j]) == 'yes':
r.insert_before(dict[i + 1][j], dict[i][j])
except:
for j in range(len(max(dict[i], dict[i + 1]))):
#print(dict[i][j], dict[i + 1][j])
if dict[i][j] == dict[i + 1][j] and r.is_exists(dict[i][j]) == 'no':
r.insert(dict[i][j])
elif dict[i][j] == dict[i + 1][j] and r.is_exists(dict[i][j]) == 'yes':
pass
elif dict[i][j] != dict[i + 1][j]:
if (r.is_exists(dict[i][j]) == 'no' or r.is_exists(dict[i + 1][j]) == 'no'):
if r.is_exists(dict[i][j]) == 'yes':
r.insert_after(dict[i][j], dict[i + 1][j])
elif r.is_exists(dict[i + 1][j]) == 'yes':
r.insert_before(dict[i + 1][j], dict[i][j])
print (''.join(map(str, r.listprint())))

Looking for my next opportunity to make change in a BIG way