Kiểm tra hai chuỗi tương đương theo điều kiện đệ quy trong Python

Cho hai chuỗi s và t cùng độ dài. Kiểm tra xem chúng có "tương đương" không theo quy tắc:

1. Chúng bằng nhau. HOẶC
2. Chia s làm s1, s2 (hai nửa liên tiếp). Chia t làm t1, t2 tương tự. Khi đó một trong hai đúng:
   • s1 tương đương đệ quy với t1 VÀ s2 tương đương đệ quy với t2.
   • s1 tương đương đệ quy với t2 VÀ s2 tương đương đệ quy với t1.

Ví dụ: s="ppqp", t="pqpp" → True.

Thuật toán

• Hàm util(s):
  • Nếu độ dài lẻ → trả về s.
  • left = util(nửa trái), right = util(nửa phải).
  • Trả về min(left+right, right+left) (so sánh lexicographic).
• Hàm chính: trả về util(s) == util(t).

Ví dụ code

def util(s):
    if len(s) & 1 != 0:
        return s
    left = util(s[0:int(len(s)/2)])
    right = util(s[int(len(s)/2):len(s)])
    return min(left + right, right + left)

def solve(s, t):
    return util(s) == util(t)

s = "ppqp"
t = "pqpp"
print(solve(s, t))

Đầu vào

"ppqp", "pqpp"

Đầu ra

True