আমাদের দুটি স্ট্রিং আছে s এবং t। আমাদের একটি স্ট্রিং merge তৈরি করতে হবে নিচের নিয়ম অনুযায়ী: যতক্ষণ না s বা t খালি হয়, নিচের অপশনগুলো থেকে একটি বেছে নিন:
যদি
sখালি না হয়, তবেs-এর প্রথম ক্যারেক্টারটিmerge-এ যোগ করুন এবংs- থেকে মুছে দিন।যদি
tখালি না হয়, তবেt-এর প্রথম ক্যারেক্টারটিmerge-এ যোগ করুন এবংt- থেকে মুছে দিন।
আমাদের যেটি তৈরি করতে পারি সেটির মধ্যে লেক্সিকোগ্রাফিক্যালি সবচেয়ে বড় merge খুঁজে বের করতে হবে।
উদাহরণস্বরূপ, ইনপুট s = "zxyxx", t = "yzxxx" হলে আউটপুট হবে zyzxyxxxxx, কারণ:
s- থেকে বেছে নিন:merge = "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-এর বাকি ৫টি x গুলো merge-এর শেষে যোগ করুন।
সমাধানের ধাপসমূহ
ans := খালি স্ট্রিংidx1 := 0, idx2 := 0idx1 < s-এর আকার এবংidx2 < t-এর আকার থাকাকালীন লুপ চালান:যদি
s[idx1] > t[idx2]হয় অথবা(s[idx1] == t[idx2] এবং s[idx1:] >= t[idx2:])হয়, তবে:ans := ans + s[idx1]idx1 := idx1 + 1
অন্যথায়, যদি
s[idx1] < t[idx2]হয় অথবা(s[idx1] == t[idx2] এবং s[idx1:] <= t[idx2:])হয়, তবে:ans := ans + t[idx2]idx2 := idx2 + 1
ans + s[idx1:] + t[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)) ইনপুট
"zxyxx", "yzxxx"
আউটপুট
zyzxyxxxxx
