Giả sử chúng ta có hai chuỗi a và b có độ dài bằng nhau. Chúng ta phải chọn một chỉ mục và tách cả hai chuỗi tại chỉ mục đã chọn đó, tách a thành hai chuỗi:a_pref và a_suff trong đó a =a_pref | a_suff và tách b thành hai chuỗi:b_pref | b_suff (| là toán tử nối) trong đó b =b_pref + b_suff. Kiểm tra xem a_pref + b_suff hoặc b_pref + a_suff có tạo thành palindrome hay không. (Bất kỳ phần tách nào có thể là một chuỗi trống)
Vì vậy, nếu đầu vào là a ="pqrst" b ="turqp", thì đầu ra sẽ là True vì chúng ta có thể tách a như ["pq", "rst"] và b như ["tu", "rqp" ], vì vậy nếu chúng ta nối a_pref với b_suff, chúng ta sẽ nhận được "pqrqp" là một palindrome.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
cho mỗi cặp (x, y) từ danh sách các cặp [(a, b), (b, a)], thực hiện
-
i:=0, j:=kích thước của x - 1
-
trong khi x [i] giống y [j] và i
0, do -
i:=i + 1
-
j:=j - 1
-
-
midx:=chuỗi con của x từ chỉ mục i đến j
-
midy:=chuỗi con của y từ chỉ mục i đến j
-
nếu midx là palindrome hoặc midy là palindrome thì
-
trả về True
-
-
-
trả về Sai
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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