পাইথনে ইনপুট শব্দে একটি শর্ট সার্কিট আছে কিনা তা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে শব্দের একটি তালিকা আছে। আমাদের চেক করতে হবে যে প্রদত্ত শব্দগুলি একটি বৃত্ত গঠনের জন্য শৃঙ্খলিত হতে পারে। একটি শব্দ A একটি শৃঙ্খলিত বৃত্তে আরেকটি শব্দ B এর সামনে স্থাপন করা যেতে পারে যদি A এর শেষ অক্ষরটি B এর প্রথম অক্ষরের সাথে অভিন্ন হয়। প্রতিটি শব্দ ব্যবহার করতে হবে এবং শুধুমাত্র একবার ব্যবহার করা যেতে পারে (প্রথম/শেষ শব্দটি বিবেচনা করা হবে না)।

সুতরাং, যদি ইনপুটটি শব্দের মত হয় =["পিঁপড়া","কুকুর","tamarind","বমিভাব","বন্দুক"], তাহলে আউটপুট হবে True।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• গ্রাফ :=একটি নতুন কী-মানের জোড়া তালিকা

• দেখা হয়েছে :=একটি নতুন সেট

• inDegree :=একটি নতুন কী-মানের জুটির তালিকা

• outDegree :=একটি নতুন কী-মানের জুড়ি তালিকা

• প্রতিটি শব্দের জন্য, করুন

  • শুরু :=শব্দ[0]

  • শেষ :=শব্দ[-1]

  • গ্রাফের শেষে সন্নিবেশ করুন [শুরু]

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

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

• outDegree প্রতিটি নোডের জন্য, করুন

  • যদি outDegree[node] inDegree[node] এর মত না হয়, তাহলে

    • রিটার্ন ফলস

• dfs(শব্দ[0,0])

• রিটার্ন সাইজ দেখা যায় যদি এটি গ্রাফের আকারের সমান হয়

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড নেবে।

  • দেখা

    এ যোগ(নোড)

  • গ্রাফ[নোড]-এ প্রতিটি শিশুর জন্য, করুন

    • যদি শিশুটি দেখা না যায়, তাহলে

    • 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