পাইথনে প্রদত্ত শর্ত অনুসারে দুটি স্ট্রিং সমতুল্য কিনা তা পরীক্ষা করুন

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

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ কোড

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