Giả sử chúng ta có hai chuỗi s và t. Chúng ta phải tạo một chuỗi được gọi là hợp nhất theo cách sau:mặc dù s hoặc t không trống, hãy chọn một trong các tùy chọn sau -
-
Nếu s không trống, thì hãy nối ký tự đầu tiên vào s để hợp nhất và xóa nó khỏi s.
-
Nếu t không trống, thì hãy nối ký tự đầu tiên vào t để hợp nhất và xóa nó khỏi t.
Vì vậy, chúng tôi phải tìm ra sự hợp nhất lớn nhất về mặt từ vựng mà chúng tôi có thể thực hiện.
Vì vậy, nếu đầu vào giống như s ="zxyxx" t ="yzxxx", thì đầu ra sẽ là zyzxyxxxxx, bởi vì
-
Chọn từ s:merge ="z", s ="xyxx", t ="yzxxx"
-
Chọn từ t:merge ="zy", s ="xyxx", t ="zxxx"
-
Chọn từ t:merge ="zyz", s ="xyxx", t ="xxx"
-
Chọn từ s:merge ="zyzx", s ="yxx", t ="xxx"
-
Chọn từ s:merge ="zyzxy", s ="xx", t ="xxx"
Sau đó, thêm 5 chữ x còn lại từ s và t vào cuối quá trình hợp nhất.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ans:=chuỗi trống
-
idx1:=0, idx2:=0
-
while idx1
-
nếu s [idx1]> t [idx2] hoặc (s [idx1] giống với t [idx2] và chuỗi con của s [từ chỉ mục idx1 đến cuối]> =chuỗi con của t [từ chỉ mục idx2 đến cuối]), thì
-
ans:=ans nối s [idx1]
-
idx1:=idx1 + 1
-
-
ngược lại khi s [idx1]
-
ans:=ans nối t [idx2]
-
idx2:=idx2 + 1
-
-
-
return ans concatenate s [from index idx1 to end] concatenate t [from index idx2 to end]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]
Đầu ra
zyzxyxxxxx