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