Python程序：检测输入单词中是否存在短路

假设我们有一列单词。我们必须检查给定的单词是否可以连接成一个环。只有当单词A的最后一个字符与单词B的第一个字符相同，单词A才能放在单词B的前面。每个单词都必须使用，并且只能使用一次（首尾单词不算）。

因此，如果输入类似于words = ["ant","dog","tamarind","nausea","gun"]，则输出为True。

为了解决这个问题，我们将遵循以下步骤：

  • graph := 一个新的键值对列表

  • seen := 一个新的集合

  • inDegree := 一个新的键值对列表

  • outDegree := 一个新的键值对列表

  • 对于words中的每个单词，执行：

    • start := word[0]

    • end := word[-1]

    • 将end插入graph[start]的末尾

    • outDegree[start] := outDegree[start] + 1

    • inDegree[end] := inDegree[end] + 1

  • 对于outDegree中的每个节点，执行：

    • 如果outDegree[node]与inDegree[node]不同，则

      • 返回False

  • dfs(words[0,0])

  • 如果seen的大小与graph的大小相同，则返回seen的大小

  • 定义一个函数dfs()。这将接受一个节点。

    • 将node添加到seen中

    • 对于graph[node]中的每个子节点，执行：

      • 如果seen中不存在子节点，则

      • dfs(子节点)

示例

让我们看下面的实现以更好地理解：

在线演示

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

更新于：2020年12月23日

84 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告