Chương trình tách 2 chuỗi để tạo palindrome trong Python

Cho 2 chuỗi a, b cùng độ dài. Chọn chỉ số cắt, tách a = a_pref + a_suff, b = b_pref + b_suff. Kiểm tra a_pref + b_suff hoặc b_pref + a_suff có phải palindrome không.

Ví dụ: a="pqrst", b="turqp" → True. Cắt: a=["pq","rst"], b=["tu","rqp"], a_pref+b_suff = "pqrqp" là palindrome.

Giải thuật (Hai con trỏ từ 2 đầu)

1. Thử 2 hướng: (a,b) và (b,a).
2. Con trỏ i=0 (đầu x), j=len(x)-1 (cuối y).
3. Trong khi x[i] == y[j] và i < len(x), j > 0: i++, j--.
4. Phần giữa: midx = x[i:j+1], midy = y[i:j+1].
5. Nếu midx hoặc midy là palindrome → True.

Ví dụ minh họa

def solve(a, b):
    for x, y in [[a, b], [b, a]]:
        i, j = 0, len(x) - 1
        while x[i] == y[j] and i < len(x) and j > 0:
            i += 1
            j -= 1
        midx = x[i:j+1]
        midy = y[i:j+1]
        if midx == midx[::-1] or midy == midy[::-1]:
            return True
    return False

a = "pqrst"
b = "turqp"
print(solve(a, b))

Đầu vào

"pqrst", "turqp"

Đầu ra

True