找出Python输入字中是否存在短路的程序
假设我们有一个单词列表。我们必须检查给定的单词是否可以链接成一个圆圈。如果只有A的最后一个字符与B的第一个字符相同，则可以将一个单词A放置在一个链环中的另一个单词B的前面。每个单词都必须使用并且只能使用一次（第一个/最后一个单词）不会被考虑）。
因此，如果输入像单词=[“ant”，“dog”，“tamarind”，“恶心”，“gun”]，则输出将为True。
在线示例
让我们看下面的实现以更好地理解-
import collections
class Solution:
def solve(self, words):
self.graph = collections.defaultdict(list)
self.seen = set()
inDegree = collections.Counter()
outDegree = collections.Counter()
for word in words:
start = word[0]
end = word[-1]
self.graph[start].append(end)
outDegree[start] += 1
inDegree[end] += 1
for node in outDegree:
if outDegree[node] != inDegree[node]:
return False
self.dfs(words[0][0])
return len(self.seen) == len(self.graph)
def dfs(self, node):
self.seen.add(node)
for child in self.graph[node]:
if child not in self.seen:
self.dfs(child)
ob = Solution()
print(ob.solve(["ant","dog","tamarind","nausea","gun"]))输入值
["ant","dog","tamarind","nausea","gun"]输出结果
True
热门推荐
10 朋友新年祝福语大全 简短
11 新年祝福语简短大方兔年
12 搬新家礼物祝福语简短
13 同学见面花束祝福语简短
14 五一假期祝福语幽默简短
15 离职欢送敬酒祝福语简短
16 对学弟的祝福语简短
17 考老师辞职祝福语简短
18 祝福语驱散霉运的话简短