পাইথনে ওয়ার্ড চেইন থেকে সার্কেল তৈরি করা যায় কিনা চেক করা

একটি ওয়ার্ড লিস্ট দেওয়া আছে। এগুলোকে চেইন করে একটি সার্কেল বানানো যায় কিনা চেক করতে হবে। ওয়ার্ড A, ওয়ার্ড B-এর সামনে থাকতে পারবে যদি A-এর শেষ অক্ষর = B-এর প্রথম অক্ষর হয়। সব ওয়ার্ড একবার ব্যবহার করতে হবে।

উদাহরণ: words = ["ant","dog","tamarind","nausea","gun"] → আউটপুট True।

সমাধানের ধাপসমূহ (অয়লার সার্কিট / গ্রাফ থিওরি)

ডিরেক্টেড গ্রাফ বানান: নোড = অক্ষর, এজ = ওয়ার্ড (স্টার্ট -> এন্ড)।
inDegree এবং outDegree কাউন্ট করুন।
প্রতিটি নোডের জন্য inDegree == outDegree হতে হবে (অয়লার সার্কিটের শর্ত)।
প্রথম ওয়ার্ডের প্রথম অক্ষর থেকে DFS/BFS চালিয়ে সব নোড ভিজিটেড কিনা চেক করুন (কানেক্টেড কম্পোনেন্ট)।
দুটি শর্ত পূরণ হলে True, অন্যথায় False।

পাইথন কোড উদাহরণ

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