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

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

इसलिए, यदि इनपुट words = ["ant","dog","tamarind","nausea","gun"] जैसा है, तो आउटपुट True होगा।

हल करने के चरण

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

• seen := एक नया सेट

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

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

• words में प्रत्येक word के लिए, करें

  • start := word[0]

  • end := word[-1]

  • end को graph[start] के अंत में डालें

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

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

• outDegree में प्रत्येक node के लिए, करें

  • यदि outDegree[node], inDegree[node] के समान नहीं है, तो False लौटाएं

• dfs(words[0][0])

• यदि seen का आकार, graph के आकार के समान है तो लौटाएं

• dfs() फ़ंक्शन परिभाषित करें। यह node लेगा।

  • seen में node जोड़ें

  • graph[node] में प्रत्येक child के लिए, करें

    • यदि child, seen में मौजूद नहीं है, तो dfs(child)

उदाहरण

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