C++-এ K- অনুরূপ স্ট্রিং

ধরুন আমাদের দুটি স্ট্রিং A এবং B আছে। এই দুটি স্ট্রিং হল K-সদৃশ (যেখানে K হল একটি অঋণাত্মক পূর্ণসংখ্যা) যদি আমরা A ঠিক K সময়ে দুটি অক্ষরের অবস্থান অদলবদল করতে পারি যাতে ফলস্বরূপ স্ট্রিংটি B হয়। তাই, আমাদের আছে দুটি অ্যানাগ্রাম A এবং B, আমাদের সবচেয়ে ছোট K খুঁজে বের করতে হবে যার জন্য A এবং B K- অনুরূপ।

সুতরাং, যদি ইনপুট A ="abc", B ="bac" এর মত হয়, তাহলে আউটপুট হবে 2।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন swapp() সংজ্ঞায়িত করুন, এটি স্ট্রিং s, i, j,
লাগবে
x :=s[i], y :=s[j]
s[i] :=y, s[j] :=x
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
A যদি B এর মত হয়, তাহলে:, ফেরত দিন 0
পরিদর্শন করা একটি সেট সংজ্ঞায়িত করুন
পরিদর্শন করা
এ প্রবেশ করান
একটি সারি q সংজ্ঞায়িত করুন, q তে A সন্নিবেশ করুন
lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −
- sz :=q এর আকার
- যখন sz অ-শূন্য হয়, প্রতিটি পুনরাবৃত্তিতে 1 দ্বারা sz কমান, −
  - curr :=q এর প্রথম উপাদান
  - q
    থেকে উপাদান মুছুন
  - i :=0
  - যখন (i
    - (i 1 দ্বারা বাড়ান)
  - j আরম্ভ করার জন্য :=i + 1, যখন j
    - যদি curr[i] curr[j] এর মত হয়, তাহলে -
      - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
    - যদি curr[j] B[i] এর সমান না হয়, তাহলে -
      - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
    - যদি curr[j] B[j] এর মত হয়, তাহলে −
      - নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
    - swapp(curr, i, j)
    - যদি curr B এর মত হয়, তাহলে −
      - ফিরুন lvl
    - ভিজিট করা কল কাউন্ট(curr) না হলে -
      - ভিজিটেড
        তে curr ঢোকান
      - q
        -এ curr সন্নিবেশ করান
    - swapp(curr, i, j)
রিটার্ন -1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int kSimilarity(string A, string B) {
      if (A == B)
      return 0;
      unordered_set<string> visited;
      visited.insert(A);
      queue<string> q;
      q.push(A);
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            string curr = q.front();
            q.pop();
            int i = 0;
            while (i < curr.size() && curr[i] == B[i])
            i++;
            for (int j = i + 1; j < curr.size(); j++) {
               if (curr[i] == curr[j])
               continue;
               if (curr[j] != B[i])
               continue;
               if (curr[j] == B[j])
               continue;
               swapp(curr, i, j);
               if (curr == B)
               return lvl;
               if (!visited.count(curr)) {
                  visited.insert(curr);
                  q.push(curr);
               }
               swapp(curr, i, j);
            }
         }
      }
      return -1;
   }
   void swapp(string &s, int i, int j) {
      char x = s[i];
      char y = s[j];
      s[i] = y;
      s[j] = x;
   }
};
main(){
   Solution ob;
   cout << (ob.kSimilarity("abc", "bac"));
}

ইনপুট

"abc", "bac"