外星人词典 Python

Question

外星词典

Link给在线判断 -> LINK

给定一个外星语言的排序字典，该字典具有标准字典的 N 个单词和 k 个起始字母。找出外星语言中字符的顺序。注意：对于特定的测试用例，可能有许多顺序，因此您可以 return 任何有效的顺序，如果函数 return 字符串的顺序正确，则输出将为 1 否则 0 表示不正确的字符串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.

我的工作代码：

 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

Answer 1

有趣的问题。你的想法是正确的，它是一个部分有序的集合你可以构建一个有向无环图并使用拓扑排序找到一个有序的顶点列表。

你的程序失败的原因是因为不是所有的字母可能有些字母不会被添加到你的vertList.

剧透： 在代码的某处添加以下行可解决问题

vlist = [chr(ord('a') + v) for v in range(K)]

一个简单的失败示例

考虑输入

2 4
baa abd

这将决定以下vertList

{"b": ["a"]}

唯一的限制是 b 必须在这个字母表中出现在 a 之前。您的代码 returns 字母表 b a，因为字母 d 不存在，您的驱动程序代码将在尝试检查您的解决方案时产生错误。在我看来，在这种情况下它应该简单地输出 0。

外星人词典 Python

Alien Dictionary Python

python-3.x

algorithm

graph

topological-sort

一个简单的失败示例