จำนวนการดำเนินการที่กำหนดขั้นต่ำที่จำเป็นในการทำให้สองสตริงเท่ากันโดยใช้ C ++

คำชี้แจงปัญหา

ให้สองสตริง str1 และ str2 ทั้งสองสตริงมีอักขระ 'a' และ 'b' ทั้งสองสายมีความยาวเท่ากัน มีหนึ่ง _ (ช่องว่าง) ในทั้งสองสตริง งานคือการแปลงสตริงแรกเป็นสตริงที่สองโดยทำจำนวนขั้นต่ำของการดำเนินการต่อไปนี้ -

หาก _ อยู่ที่ตำแหน่ง I แล้ว _ สามารถสลับกับอักขระที่ตำแหน่ง i+1 หรือ i-1
หากอักขระที่ตำแหน่ง i+1 และ i+2 ต่างกัน _ สามารถสลับกับอักขระที่ตำแหน่ง i+1 หรือ i+2
ในทำนองเดียวกัน หากอักขระที่ตำแหน่ง i-1 และ i-2 ต่างกัน _ สามารถสลับกับอักขระที่ตำแหน่ง i-1 หรือ i-2

ถ้า str1 =“aba_a” และ str2 =“_baaa” เราต้องการ 2 การเคลื่อนไหวเพื่อแปลง str1 เป็น str2 -

<ก่อน>1. str1 =“ab_aa” (สลับ str1[2] กับ str1[3])2 str2 =“_baaa” (สลับ str1[0] เป็น str1[2])

อัลกอริทึม

<ก่อน>1. ใช้ Breadth First Search อย่างง่ายบนสตริง และองค์ประกอบของคิวที่ใช้สำหรับ BFS จะมีคู่ str, pos โดยที่ pos คือตำแหน่งของ _ ในสตริง str.2 รักษาแผนที่คือ 'vis' ซึ่งจะเก็บสตริงเป็นคีย์และย้ายขั้นต่ำเพื่อไปที่สตริงเป็นค่า สำหรับทุกสตริง str จากคิว ให้สร้างสตริงใหม่ tmp ตามเงื่อนไขสี่ข้อที่กำหนดและอัปเดตแผนที่ vis เป็น vis[tmp] =vis[str] + 1.4 ทำซ้ำขั้นตอนข้างต้นจนกว่าคิวจะว่างหรือสร้างสตริงที่ต้องการ เช่น tmp ==B5 หากสตริงที่ต้องการถูกสร้างขึ้น ให้ส่งคืน vis[str] + 1 ซึ่งเป็นจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการเปลี่ยน A เป็น B

ตัวอย่าง

#include #include #include 
#include using namespace std;int transformString (string str, string f){ unordered_map vis; int n; n =str.ความยาว(); int pos =0; สำหรับ (int i =0; i > q; q.push({ str, ตำแหน่ง }); vis[str] =0; ในขณะที่ (!q.empty()) { string ss =q.front().first; int pp =q.front().วินาที; int dist =vis[ss]; q.ป๊อป(); ถ้า (pp>
 0) { สลับ (ss [pp], ss [pp - 1]); if (!vis.count(ss)) { if (ss ==f) { return dist + 1; หยุดพัก; } vis[ss] =dist + 1; q.push({ ss, pp - 1 }); } สลับ (ss[pp], ss[pp - 1]); } if (pp 
 1 &&ss[pp - 1] !=ss[pp - 2]) { swap(ss[pp], ss[pp - 2]); if (!vis.count(ss)) { if (ss ==f) { return dist + 1; หยุดพัก; } vis[ss] =dist + 1; q.push({ ss, pp - 2 }); } สลับ (ss[pp], ss[pp - 2]); } if (pp  ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ย้ายขั้นต่ำที่ต้องการ:2