मान लीजिए हमारे पास समान आकार के दो स्ट्रिंग्स s और t हैं। हमें जांचना है कि s और t समतुल्य हैं या नहीं। जांचने के लिए कुछ शर्तें हैं:
- वे दोनों समान हैं। या,
- यदि हम s को समान आकार के दो सन्निहित सबस्ट्रिंग्स में विभाजित करते हैं और सबस्ट्रिंग्स s1 और s2 हैं और t को भी उसी तरह विभाजित करते हैं, s को t1 और t2 में, तो निम्नलिखित में से एक मान्य होना चाहिए:
- s1 पुनरावर्ती रूप से t1 के समतुल्य है और s2 पुनरावर्ती रूप से t2 के समतुल्य है
- s1 पुनरावर्ती रूप से t2 के समतुल्य है और s2 पुनरावर्ती रूप से t1 के समतुल्य है
तो, यदि इनपुट s = "ppqp" t = "pqpp" जैसा है, तो आउटपुट True होगा क्योंकि यदि हम 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, इसलिए वे पुनरावर्ती रूप से समतुल्य हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- util() फ़ंक्शन परिभाषित करें। यह s लेगा
- यदि s का आकार विषम है, तो
- s लौटाएं
- left := util(s का बायां आधा भाग)
- right := util(s का दायां आधा भाग)
- (left concatenate right) और (right concatenate left) का न्यूनतम लौटाएं
- मुख्य विधि से true लौटाएं जब util(s) util(t) के समान हो अन्यथा false
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण कोड
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
