外星词典 Python

Question

外星词典 Python

Shu*_*har 6 algorithm graph topological-sort python-3.x

外星人词典

链接到在线判断-> LINK

给定一个已排序的外语词典，它具有标准词典的 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.

Run Code Online (Sandbox Code Playgroud)

我的工作代码：

 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)

Run Code Online (Sandbox Code Playgroud)

我的问题：

对于示例中给出的测试用例，代码运行良好，但失败了 ["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'

Run Code Online (Sandbox Code Playgroud)

在其他一些 IDE 中运行：

如果我使用其他一些 IDE 明确给出这个输入，那么我得到的输出是 b d a c