python-3.x - 外星人字典 Python
问题描述
外星人词典
在线评委链接 -> 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.
我的工作代码:
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
解决方案
有趣的问题。你的想法是正确的,它是一个部分有序的集合,你可以构建一个有向无环图并使用拓扑排序找到一个有序的顶点列表。
你的程序失败的原因是因为不是所有的字母都可能有一些字母不会被添加到你的vertList
.
剧透:在代码中的某处添加以下行可以解决问题
vlist = [chr(ord('a') + v) for v in range(K)]
一个简单的失败示例
考虑输入
2 4
baa abd
这将确定以下内容vertList
{"b": ["a"]}
唯一的限制是b
必须a
在这个字母表中出现。您的代码返回字母b a
,因为字母 d 不存在,所以驱动程序代码在尝试检查您的解决方案时会产生错误。在我看来,在这种情况下它应该简单地输出 0。
推荐阅读
- javascript - 本地机器上的 Nodejs webhook 服务器
- mockito - Mockito doNothing with Mockito.mockStatic
- microsoft-graph-api - 使用 Microsoftgraph 的威胁评估请求的 RestAPI 问题
- mysql - 从重复值中选择行,其中字段从未更改
- assembly - EMU8086 将 32 位数除以 16 位数给出意外的 0 余数
- html - 如何在 Power BI 中显示 HTML 页面
- javascript - 在 highcharts 上绘制数据和时区反应
- awk - 当条件为真时从另一个文件添加行
- c# - 如何将 url 重定向到特定端点
- c++ - 如何获取比例因子以获得真实的屏幕分辨率?