【python-leetcode269-拓扑排序】火星字典
【python-leetcode269-拓扑排序】火星字典
西西嘛呦
发布于 2020-08-26 10:31:11
发布于 2020-08-26 10:31:11
现有一种使用字母的全新语言，这门语言的字母顺序与英语顺序不同。假设，您并不知道其中字母之间的先后顺序。但是，会收到词典中获得一个 不为空的 单词列表。因为是从词典中获得的，所以该单词列表内的单词已经 按这门新语言的字母顺序进行排序。您需要根据这个输入的列表，还原出此语言中已知的字母顺序。 例如：
输入：
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]输出：
正确的顺序是：“wertf”
解题：意思是按照单词的顺序排序了。比如wrt和wrf，wrt排在wrf前面，说明优先级t>f，依次类推则有：
t->f
w->e
r->t
e->r
最终则有顺序：wertf
比较麻烦的就是如何转换成字符间的顺序格式，之后用拓扑排序就好了。
class Solution:
def alienOrder(self,words):
#chars用于获取字母集合
chars=set(''.join(words))
print(chars)
#用于存储入度
degrees={x:0 for x in chars}
from collections import defaultdict
#用于存储优先级
graph=defaultdict(list)
#pair是从上到下两两匹对
for pair in zip(words,words[1:]):
print(pair)
#x,y依次取出匹对的字母
for x,y in zip(*pair):
print(x,y)
if x!=y:
#建立优先级关系
graph[x].append(y)
#入度增加1
degrees[y]+=1
break
print(degrees)
print(graph)
queue=[]
for i in chars:
if degrees[i] == 0:
queue.append(i)
res=""
while queue:
x=queue.pop(0)
res+=x
for i in graph[x]:
degrees[i]-=1
if degrees[i]==0:
queue.append(i)
return res*(set(res)==chars)
s=Solution()
print(s.alienOrder([
"wrt",
"wrf",
"er",
"ett",
"rftt"
]))结果：
第二种方法：使用深度优先遍历
class Solution:
def alienOrder(self,words):
#chars用于获取字母集合
chars=set(''.join(words))
print(chars)
#用于存储入度
degrees={x:0 for x in chars}
from collections import defaultdict
#用于存储优先级
graph=defaultdict(list)
#pair是从上到下两两匹对
for pair in zip(words,words[1:]):
print(pair)
#x,y依次取出匹对的字母
for x,y in zip(*pair):
print(x,y)
if x!=y:
#建立优先级关系
graph[x].append(y)
#入度增加1
degrees[y]+=1
break
print(degrees)
print(graph)
lis=[]
for i in chars:
if degrees[i] == 0:
lis.append(i)
res=""
while lis:
tmp=[]
for ch in lis:
res+=ch
for c in graph[ch]:
degrees[c]-=1
if degrees[c]==0:
tmp.append(c)
del graph[ch]
lis=tmp
return res if len(res)==len(chars) else ""
s=Solution()
print(s.alienOrder([
"wrt",
"wrf",
"er",
"ett",
"rftt"
]))参考：https://www.jianshu.com/p/ee280c838f2d
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-04-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读