जांचें कि पायथन में दी गई स्थिति के अनुसार दो तार समकक्ष हैं या नहीं

मान लीजिए कि हमारे पास समान आकार के दो तार s और t हैं। हमें जांचना है कि s और t समतुल्य हैं या नहीं। जाँच करने के लिए कुछ शर्तें हैं:

• वे दोनों बराबर हैं। या,
• यदि हम s को समान आकार के दो सन्निहित सबस्ट्रिंग में विभाजित करते हैं और सबस्ट्रिंग s1 और s2 हैं और t को समान, s को t1 और t2 में विभाजित करते हैं, तो निम्न में से एक मान्य होना चाहिए:
  • s1 पुनरावर्ती रूप से t1 के समतुल्य है और s2 पुनरावर्ती रूप से t2 के समतुल्य है
  • s1 पुनरावर्ती रूप से t2 के समतुल्य है और s2 पुनरावर्ती रूप से t1 के समतुल्य है

इसलिए, यदि इनपुट s ="ppqp" t ="pqpp" जैसा है, तो आउटपुट सही होगा जैसे कि हम s और t को दो भागों s1 ="pp", s2 ="qp" और t1 ="pq" में विभाजित करते हैं। ", t2 ="pp", यहाँ s1 =t2 और यदि हम s2 और t1 को दो भागों में विभाजित करते हैं s21 ="q", s22 ="p", t11 ="p", t12 ="q", यहाँ भी s21 =t12 और s22 =t11, इसलिए वे पुनरावर्ती समकक्ष हैं।

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

• उपयोग() फ़ंक्शन को परिभाषित करें। इसमें लगेगा
• यदि s का आकार विषम है, तो
  • वापसी
• बाएं:=उपयोग (ओं का बायां आधा भाग)
• दाएं:=उपयोग (ओं का दायां आधा भाग)
• रिटर्न न्‍यूनतम (बाएं समवर्ती दाएं), (दाएं समवर्ती बाएं)
• मुख्य विधि से सही रिटर्न जब उपयोग (ओं) के समान है (टी) अन्यथा गलत है

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण कोड

def util(s):
   if len(s) & 1 != 0:
      return s
 
   left = util(s[0:int(len(s) / 2)])
   right = util(s[int(len(s) / 2):len(s)])
 
   return min(left + right, right + left)
 
def solve(s,t):
   return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

इनपुट

"ppqp", "pqpp"

आउटपुट

True