Giả sử chúng ta có hai chuỗi s và t có cùng kích thước. Chúng ta phải kiểm tra xem s và t có tương đương hay không. Có một số điều kiện để kiểm tra:
- Cả hai đều bằng nhau. Hoặc,
- Nếu chúng ta chia s thành hai chuỗi con liền nhau có cùng kích thước và các chuỗi con là s1 và s2 và cũng chia t tương tự như, s thành t1 và t2, thì một trong những điều sau đây sẽ hợp lệ:
- s1 đệ quy tương đương với t1 và s2 đệ quy tương đương với t2
- s1 đệ quy tương đương với t2 và s2 đệ quy tương đương với t1
Vì vậy, nếu đầu vào là s ="ppqp" t ="pqpp", thì đầu ra sẽ là Đúng như khi chúng ta chia s và t thành hai phần s1 ="pp", s2 ="qp" và t1 ="pq ", t2 =" pp ", ở đây là s1 =t2 và nếu chúng ta chia s2 và t1 thành hai phần thì s21 =" q ", s22 =" p ", t11 =" p ", t12 =" q ", ở đây cũng là s21 =t12 và s22 =t11, vì vậy chúng tương đương đệ quy.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm use (). Điều này sẽ mất s
- nếu kích thước của s là lẻ, thì
- trả lại s
- left:=use (nửa phần bên trái của s)
- right:=use (nửa bên phải của s)
- trả về giá trị tối thiểu (bên trái nối bên phải), (bên trái nối bên phải)
- Từ phương thức main trả về true khi use (các) giống như use (t), ngược lại là false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Mã mẫu
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