Giả sử chúng ta có hai chuỗi s và t. Hai chuỗi này giống nhau K nếu chúng ta có thể hoán đổi vị trí của hai chữ cái trong s đúng K lần để chuỗi kết quả là t. Vì vậy, chúng ta có hai phép đảo chữ s và t, chúng ta phải tìm K nhỏ nhất mà s và t tương tự K.
Vì vậy, nếu đầu vào là s ="abc" t ="bac", thì đầu ra sẽ là 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàng xóm của hàm (). Thao tác này sẽ lấy new_data
-
đối với mỗi chỉ mục i và giá trị c trong new_data, hãy thực hiện
-
nếu c không giống với t [i], thì
-
đi ra từ vòng lặp
-
-
-
đối với j trong phạm vi i + 1 đến kích thước của new_data - 1, thực hiện
-
nếu u [j] giống với t [i] thì
-
trao đổi new_data [i] new_data [j]
-
tạo một chuỗi bằng cách kết hợp tất cả các phần tử từ new_data và quay lại, từ lần gọi tiếp theo, bắt đầu lại từ khu vực này
-
trao đổi new_data [i] new_data [j]
-
-
-
Từ phương thức chính, thực hiện như sau:
-
q:=tạo một hàng đợi và chèn cặp (s, 0)
-
đã thấy:=một tập hợp mới từ s
-
trong khi q không trống, thực hiện
-
(u, swap_cnt):=mục đầu tiên của q và xóa nó khỏi q
-
nếu bạn giống với t, thì
-
trả về swap_cnt
-
-
đối với mỗi v trong các hàng xóm (u dưới dạng danh sách), hãy thực hiện
-
nếu v không được nhìn thấy, thì
-
đánh dấu v như đã thấy
-
insert (v, swap_cnt + 1) vào cuối q
-
-
-
-
trả về 0
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
from collections import deque
def solve(s, t):
def swap(data, i, j):
data[i], data[j] = data[j], data[i]
def neighbors(new_data):
for i, c in enumerate(new_data):
if c != t[i]: break
for j in range(i+1, len(new_data)):
if u[j] == t[i]:
swap(new_data, i, j)
yield "".join(new_data)
swap(new_data, i, j)
q = deque([(s, 0)])
seen = set(s)
while q:
u, swap_cnt = q.popleft()
if u == t:
return swap_cnt
for v in neighbors(list(u)):
if v not in seen:
seen.add(v)
q.append((v, swap_cnt+1))
return 0
s = "abc"
t = "bac"
print(solve(s, t)) Đầu vào
"abc, bac"
Đầu ra
1