Cho 2 chuỗi a, b và chuỗi merge. Gộp theo quy tắc:
- a không rỗng -> lấy ký tự đầu a vào merge.
- b không rỗng -> lấy ký tự đầu b vào merge.
- Cả 2 không rỗng -> so sánh lexicographic: chuỗi lớn hơn lấy ký tự đầu tiên.
- Trả về merge.
Ví dụ
Input: a="bacaa", b="abcaa"
Output: "babcacaaaa" (hoặc "bacabcaaaa" tùy logic)
Giải thích: a > b theo lexicographic, lấy 'b' từ a, sau đó lần lượt từ a,b...
Cách giải
Đệ quy/iterative: so sánh a và b, chuỗi lớn hơn lấy ký tự đầu, cắt bỏ ký tự đó, lặp cho đến khi một chuỗi rỗng, nối phần còn lại.
Ví dụ
def concatenateLargest(a, b):
ans = ""
while a and b:
if a > b:
ans += a[0]
a = a[1:]
else:
ans += b[0]
b = b[1:]
ans += a
ans += b
return ans
a = "bacaa"
b = "abcaa"
print(concatenateLargest(a, b))Kết quả
bacabcaaaa
Hai chuỗi gộp thành "bacabcaaaa" theo quy tắc lexicographic lớn nhất.