ปัญหา
สตริง s, t เป็น Anagrams K-Similar: สลับตัวอักษรใน s ทั้งหมด K ครั้ง ได้ t หา K น้อยที่สุด
ตัวอย่าง
s = "abc", t = "bac" → Output: 1 (Swap a↔b)
อัลกอริทึม (BFS + Pruning)
- BFS จาก s: State = String, Level = Swap Count
- Neighbors: หา Index i แรกที่ s[i] ≠ t[i], ลอง Swap i กับ j>i ที่ s[j] == t[i]
- Pruning: Swap เฉพาะที่แก้ไข Mismatch แรก (Optimal)
- Visited Set ป้องกัน Loop
- เจอ t → Return Level
ตัวอย่างโค้ด
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ความซับซ้อน
- Time: O(n! / (duplicates!)) Worst Case แต่ Pruning ทำให้เร็วมากในทางปฏิบัติ
- Space: O(States)
- n ≤ 8-10 ใช้ได้สบาย
