Инопланетный словарь Python

Словарь пришельцев

Ссылка на онлайн-судью - ›ССЫЛКА

Дан отсортированный словарь чужого языка, имеющий N слов и k начальных алфавитов стандартного словаря. Найдите порядок символов на инопланетном языке. Примечание. Для конкретного тестового примера может быть возможно множество заказов, поэтому вы можете вернуть любой допустимый порядок, и на выходе будет 1, если порядок строки, возвращаемой функцией, правильный, иначе 0 означает возвращенную неверную строку.

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.

Мой рабочий код:

 from collections import defaultdict
class Solution:

    def __init__(self):
        self.vertList = defaultdict(list)

    def addEdge(self,u,v):
        self.vertList[u].append(v)
    
    def topologicalSortDFS(self,givenV,visited,stack):
        visited.add(givenV)

        for nbr in self.vertList[givenV]:
            if nbr not in visited:
                self.topologicalSortDFS(nbr,visited,stack)
        stack.append(givenV)

    def findOrder(self,dict, N, K):
        list1 = dict
        for i in range(len(list1)-1):
            word1 = list1[i]
            word2 = list1[i+1]
            rangej = min(len(word1),len(word2))
            for j in range(rangej):
                if word1[j] != word2[j]:
                    u = word1[j]
                    v = word2[j]
                    self.addEdge(u,v)
                    break
        stack = []
        visited = set()
        vlist = [v for v in self.vertList]
        for v in vlist:
            if v not in visited:
                self.topologicalSortDFS(v,visited,stack)
        result = " ".join(stack[::-1])

        return result
                
                
#{ 
#  Driver Code Starts
#Initial Template for Python 3

class sort_by_order:
    def __init__(self,s):
        self.priority = {}
        for i in range(len(s)):
            self.priority[s[i]] = i
    
    def transform(self,word):
        new_word = ''
        for c in word:
            new_word += chr( ord('a') + self.priority[c] )
        return new_word
    
    def sort_this_list(self,lst):
        lst.sort(key = self.transform)

if __name__ == '__main__':
    t=int(input())
    for _ in range(t):
        line=input().strip().split()
        n=int(line[0])
        k=int(line[1])
        
        alien_dict = [x for x in input().strip().split()]
        duplicate_dict = alien_dict.copy()
        ob=Solution()
        order = ob.findOrder(alien_dict,n,k)
        
        x = sort_by_order(order)
        x.sort_this_list(duplicate_dict)
        
        if duplicate_dict == alien_dict:
            print(1)
        else:
            print(0)

Моя проблема:

Код работает нормально для тестовых случаев, приведенных в примере, но не работает для ["baa", "abcd", "abca", "cab", "cad"]

Для этого ввода возникает следующая ошибка:

Runtime Error:
Runtime ErrorTraceback (most recent call last):
  File "/home/e2beefe97937f518a410813879a35789.py", line 73, in <module>
    x.sort_this_list(duplicate_dict)
  File "/home/e2beefe97937f518a410813879a35789.py", line 58, in sort_this_list
    lst.sort(key = self.transform)
  File "/home/e2beefe97937f518a410813879a35789.py", line 54, in transform
    new_word += chr( ord('a') + self.priority[c] )
KeyError: 'f'

Работает в другой среде IDE:

Если я явно предоставлю этот ввод, используя другую среду IDE, то получаю результат b d a c