Hai chuỗi s, t là K-similar nếu hoán đổi 2 ký tự trong s đúng K lần thì được t. Cho s, t là anagram. Tìm K nhỏ nhất.
Ví dụ: s = "abc", t = "bac" → output = 1 (hoán đổi a,b).
Giải thuật (BFS trên trạng thái chuỗi)
- Trạng thái = chuỗi hiện tại. BFS từ s.
- Hàm neighbors(u): tìm i đầu tiên u[i] != t[i]. Thử hoán đổi u[i] với u[j] (j>i) sao cho u[j] == t[i]. Sinh neighbor mới.
- Dùng queue (deque) + set seen. Trả về swap_cnt khi u == t.
Code Python
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 new_data[j] == t[i]:
swap(new_data, i, j)
yield "".join(new_data)
swap(new_data, i, j)
q = deque([(s, 0)])
seen = {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)) # 1
Đầu vào / Đầu ra
Input: "abc", "bac"
Output: 1