ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে। আমাদের নিম্নলিখিত উপায়ে মার্জ নামে একটি স্ট্রিং তৈরি করতে হবে:যখন s বা t খালি নয়, নিম্নলিখিত বিকল্পগুলির মধ্যে একটি নির্বাচন করুন -
-
যদি s খালি না হয়, তাহলে s-এর মধ্যে প্রথম অক্ষর যোগ করুন এবং s থেকে মুছে ফেলুন।
-
যদি t খালি না হয়, তাহলে t-এর মধ্যে প্রথম অক্ষর যোগ করুন এবং t থেকে এটি মুছে ফেলুন।
তাই আমাদের খুঁজে বের করতে হবে আভিধানিকভাবে সবচেয়ে বড় মার্জ যা আমরা করতে পারি।
সুতরাং, যদি ইনপুটটি s ="zxyxx" t ="yzxxx" এর মত হয়, তাহলে আউটপুট হবে zyzxyxxxxxx, কারণ
-
s থেকে বেছে নিন:মার্জ ="z", s ="xyxx", t ="yzxxx"
-
t থেকে বেছে নিন:merge ="zy", s ="xyxx", t ="zxxx"
-
t থেকে বেছে নিন:merge ="zyz", s ="xyxx", t ="xxx"
-
s থেকে বেছে নিন:merge ="zyzx", s ="yxx", t ="xxx"
-
s থেকে বেছে নিন:merge ="zyzxy", s ="xx", t ="xxx"
তারপর মার্জের শেষে s এবং t থেকে অবশিষ্ট 5 x যোগ করুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=ফাঁকা স্ট্রিং
-
idx1 :=0, idx2 :=0
-
যখন idx1
-
যদি s[idx1]> t[idx2] বা (s[idx1] হয় t[idx2] এবং s-এর সাবস্ট্রিং [index idx1 থেকে end]>=t[index idx2 থেকে শেষ পর্যন্ত] এর সাবস্ট্রিং), তাহলে
-
ans :=ans concatenate s[idx1>
-
idx1 :=idx1 + 1
-
-
অন্যথায় যখন s[idx1]
-
ans :=ans concatenate t[idx2]
-
idx2 :=idx2 + 1
-
-
-
[index idx1 থেকে end] concatenate t[index idx2 থেকে শেষ পর্যন্ত]
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(s, t):
ans = ""
idx1 = idx2 = 0
while(idx1<len(s) and idx2<len(t)):
if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
ans+=s[idx1]
idx1+=1
elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
ans+=t[idx2]
idx2+=1
return ans+s[idx1:]+t[idx2:]
s = "zxyxx"
t = "yzxxx"
print(solve(s, t))
ইনপুট
[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]
আউটপুট
zyzxyxxxxx
