पायथन में इनपुट शब्दों में शॉर्ट सर्किट है या नहीं यह पता लगाने के लिए कार्यक्रम

मान लीजिए हमारे पास शब्दों की एक सूची है। हमें यह जांचना है कि दिए गए शब्दों को एक वृत्त बनाने के लिए जंजीर से बांधा जा सकता है। एक शब्द ए को दूसरे शब्द बी के सामने एक जंजीर सर्कल में रखा जा सकता है यदि केवल ए का अंतिम अक्षर बी के पहले अक्षर के समान है। प्रत्येक शब्द का उपयोग किया जाना है और केवल एक बार उपयोग किया जा सकता है (पहला/अंतिम शब्द विचार नहीं किया जाएगा)।

इसलिए, यदि इनपुट शब्दों की तरह है =["चींटी", "कुत्ता", "इमली", "मतली", "बंदूक"], तो आउटपुट सही होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ग्राफ़ :=एक नई कुंजी-मान जोड़ी सूची

• देखा :=एक नया सेट

• inDegree :=एक नया की-वैल्यू पेयर लिस्ट

• आउटडिग्री:=एक नई कुंजी-मूल्य जोड़ी सूची

• शब्दों में प्रत्येक शब्द के लिए, करें

  • प्रारंभ:=शब्द[0]

  • अंत:=शब्द[-1]

  • ग्राफ़ के अंत में अंत डालें[प्रारंभ]

  • आउटडिग्री [शुरू]:=आउटडिग्री [शुरू] + 1

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

• आउटडिग्री में प्रत्येक नोड के लिए, करें

  • अगर आउटडिग्री [नोड] इनडिग्री [नोड] के समान नहीं है, तो

    • झूठी वापसी

• dfs(शब्द[0,0])

• यदि यह ग्राफ़ के आकार के समान है तो वापसी का आकार देखें

• फ़ंक्शन को परिभाषित करें 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