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” হয়, তাহলে str1-কে str2-এ রূপান্তর করতে আমাদের 2টি চাল প্রয়োজন। <পূর্ব>1. str1 =“ab_aa” (str1[2] এর সাথে str1[3] অদলবদল করা হয়েছে)2। str2 ="_baaa" (str1[2] এর সাথে str1[0] অদলবদল করা হয়েছে)

অ্যালগরিদম

<পূর্ব>1. স্ট্রিংয়ের উপর একটি সাধারণ ব্রেডথ ফার্স্ট সার্চ প্রয়োগ করুন এবং BFS-এর জন্য ব্যবহৃত সারির একটি উপাদানে জোড়া str, pos থাকবে যেখানে স্ট্রিং str.2-এ pos হল _ এর অবস্থান। এছাড়াও 'vis' নামে একটি মানচিত্র বজায় রাখুন যা স্ট্রিংটিকে কী হিসাবে সংরক্ষণ করবে এবং স্ট্রিংকে মান হিসাবে পেতে সর্বনিম্ন পদক্ষেপগুলি।3। কিউ থেকে প্রতিটি স্ট্রিং str এর জন্য, প্রদত্ত চারটি শর্তের উপর ভিত্তি করে একটি নতুন স্ট্রিং tmp তৈরি করুন এবং ভিস ম্যাপটিকে vis[tmp] =vis[str] + 1.4 হিসাবে আপডেট করুন। উপরের ধাপগুলি পুনরাবৃত্তি করুন যতক্ষণ না সারিটি খালি হয় বা প্রয়োজনীয় স্ট্রিং তৈরি হয় যেমন tmp ==B5। যদি প্রয়োজনীয় স্ট্রিং তৈরি করা হয়, তাহলে vis[str] + 1 ফেরত দিন যা A থেকে B পরিবর্তন করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন।

উদাহরণ

#include #include #include 
#include  namespace ব্যবহার করে std;int transformString(string str, string f){ unordered_map vis; int n; n =str.length(); int pos =0; জন্য (int i =0; i > q; q.push({ str, pos}); vis[str] =0; যখন (!q.empty()) { স্ট্রিং ss =q.front().first; int pp =q.front().second; int dist =vis[ss]; q.pop(); যদি (pp>
 0) { swap(ss[pp], ss[pp - 1]); if (!vis.count(ss)) { if (ss ==f) { dist + 1 ফেরত দিন; বিরতি } vis[ss] =dist + 1; q.push({ ss, pp - 1 }); } swap(ss[pp], ss[pp - 1]); } যদি (pp 
 1 &&ss[pp - 1] !=ss[pp - 2]) { swap(ss[pp], ss[pp - 2]); if (!vis.count(ss)) { if (ss ==f) { dist + 1 ফেরত দিন; বিরতি } vis[ss] =dist + 1; q.push({ ss, pp - 2 }); } swap(ss[pp], ss[pp - 2]); } যদি (pp  আউটপুট
 
 আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
 তৈরি করে সর্বনিম্ন প্রয়োজনীয় পদক্ষেপ:2