สมมติว่าเรามีสองสตริง s และ t สตริงทั้งสองนี้เป็น K-similar หากเราสามารถสลับตำแหน่งของตัวอักษรสองตัวใน s ตรง K ครั้งเพื่อให้สตริงผลลัพธ์เป็น t ดังนั้น เรามีแอนนาแกรมสองตัว s และ t เราต้องหา K ที่เล็กที่สุดที่ s และ t เป็น K-similar
ดังนั้น หากอินพุตเป็น s ="abc" t ="bac" ผลลัพธ์จะเป็น 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชั่นเพื่อนบ้าน() นี่จะใช้เวลา new_data
-
สำหรับแต่ละดัชนี i และค่า c ใน new_data ให้ทำ
-
ถ้า c ไม่เหมือนกับ t[i] แล้ว
-
ออกจากวง
-
-
-
สำหรับ j ในช่วง i+1 ถึงขนาดของ new_data - 1 ทำ
-
ถ้า u[j] เหมือนกับ t[i] แล้ว
-
แลกเปลี่ยน new_data[i] new_data[j]
-
สร้างสตริงโดยการรวมองค์ประกอบทั้งหมดจาก new_data แล้วกลับมาเริ่มใหม่อีกครั้งจากพื้นที่นี้จากการโทรครั้งถัดไป
-
แลกเปลี่ยน new_data[i] new_data[j]
-
-
-
จากวิธีหลัก ให้ทำดังนี้:
-
q :=สร้างหนึ่งคิวและแทรกคู่ (s, 0)
-
เห็น :=ชุดใหม่จาก s
-
ในขณะที่ q ไม่ว่างให้ทำ
-
(u, swap_cnt) :=รายการแรกของ q และลบออกจาก q
-
ถ้าคุณเหมือนกับ t แล้ว
-
ส่งคืน swap_cnt
-
-
สำหรับแต่ละ v ในเพื่อนบ้าน (ตามรายการ) ทำ
-
ถ้าไม่เห็น v แล้ว
-
ทำเครื่องหมาย v ตามที่เห็น
-
แทรก (v, swap_cnt+1) ต่อท้าย q
-
-
-
-
คืนค่า 0
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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)) อินพุต
"abc, bac"
ผลลัพธ์
1
