找出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