Pythonの入力ワードに短絡があるかどうかを調べるプログラム

単語のリストがあるとします。与えられた単語が連鎖して円を形成できることを確認する必要があります。 Aの最後の文字だけがBの最初の文字と同一である場合、単語Aは連鎖円内の別の単語Bの前に配置できます。すべての単語を使用する必要があり、1回だけ使用できます（最初/最後の単語）考慮されません）。

したがって、入力がwords =["ant"、 "dog"、 "tamarind"、 "nausea"、 "gun"]の場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• グラフ：=新しいキーと値のペアのリスト

• 見た：=新しいセット

• inDegree：=新しいキーと値のペアのリスト

• outDegree：=新しいキーと値のペアのリスト

• 単語の単語ごとに、実行します

  • start：=word [0]

  • 終了：=単語[-1]

  • グラフの最後にendを挿入[start]

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

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

• outDegreeのノードごとに、実行します

  • outDegree[node]がinDegree[node]と同じでない場合、

    • Falseを返す

• dfs（words [0,0]）

• グラフのサイズと同じ場合に表示される戻りサイズ

• 関数dfs（）を定義します。これはノードを取ります。

  • add（node）in saw

  • グラフ[ノード]の子ごとに、実行

    • 子供が見られない場合は

    • 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