মান লিজিয়ে আমাদের দুটি স্ট্রিং আছে s এবং t। আমরা merge নামক একটি স্ট্রিং নিচেরভাবে তৈরি করতে চাই: যতক্ষণ s বা t খালি নয়, নিচের অপশনগুলো থেকে একটি বাছাই করুন:
যদি
sখালি না হয়, তবেs-এর প্রথম ক্যারেক্টারmerge-এ অ্যাপেন্ড করুন এবংs-থেকে মুছে দিন।যদি
tখালি না হয়, তবেt-এর প্রথম ক্যারেক্টারmerge-এ অ্যাপেন্ড করুন এবংt-থেকে মুছে দিন।
শেষে, আমাদের যে লেক্সিকোগ্রাফিক্যালি সর্বোচ্চ merge তৈরি করা যায় সেটি বের করতে হবে।
যেমন, ইনপুট হলে s = "zxyxx" এবং t = "yzxxx", তবে আউটপুট হবে "zyzxyxxxxx"।
সমাধানের ধাপসমূহ
a := 0, b := 0merge := খালি স্ট্রিংW1 := len(s)W2 := len(t)a < W1 and b < W2থাকা পর্যন্ত:যদি
s[a:] > t[b:]হয়, তবে:merge := merge + s[a]a := a + 1
অন্যথায়,
merge := merge + t[b]b := b + 1
merge + s[a:] + t[b:]রিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
def solve(s, t):
a = b = 0
merge = ""
W1 = len(s)
W2 = len(t)
while a < W1 and b < W2:
if s[a:] > t[b:]:
merge += s[a]
a += 1
else:
merge += t[b]
b += 1
return merge + s[a:] + t[b:]
s = "zxyxx"
t = "yzxxx"
print(solve(s, t))ইনপুট
"zxyxx", "yzxxx"
আউটপুট
zyzxyxxxxx
