মান লেন, আমাদের কাছে একই সাইজের দুটি স্ট্রিং s এবং t আছে। আমাদের যাচাই করতে হবে s এবং t সমতুল্য কিনা। কিছু শর্ত আছে যেগুলো যাচাই করতে হবে:
- এরা দুটোই সমান। অথবা,
- যদি s কে একই সাইজের দুটি সংলগ্ন সাবস্ট্রিং-এ ভাগ করা হয় এবং সাবস্ট্রিংগুলো s1 এবং s2 এবং t কেও একইভাবে 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 + right) এবং (right + left)-এর মিনিমাম।
- মূল মেথড থেকে util(s) == util(t) হলে true রিটার্ন করুন অন্যথায় 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
