Giả sử chúng ta có hai chuỗi s và t. Chúng tôi muốn tạo một chuỗi được gọi là hợp nhất theo cách sau:trong khi 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.
Cuối cùng, chúng ta phải tìm ra sự hợp nhất lớn nhất về mặt từ vựng mà chúng ta có thể tạo thành.
Vì vậy, nếu đầu vào là s ="zxyxx" t ="yzxxx", thì đầu ra sẽ là "zyzxyxxxxx"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
a:=0, b:=0
-
hợp nhất:=chuỗi trống
-
W1:=kích thước của s
-
W2:=kích thước của t
-
trong khi a
-
nếu chuỗi con của s từ chỉ mục a đến cuối> chuỗi con của t từ chỉ mục b đến cuối, thì
-
merge:=merge concatenate s [a]
-
a:=a + 1
-
-
nếu không,
-
merge:=merge concatenate t [b]
-
b:=b + 1
-
-
-
trả về kết hợp ghép nối (chuỗi con của s từ chỉ mục a đến cuối) nối (chuỗi con của t từ chỉ mục b đến cuối)
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):
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)) Đầu vào
"zxyxx", "yzxxx"
Đầu ra
zyzxyxxxxx