K-সদৃশ স্ট্রিংর জন্য K মান খুঁজে বের করার প্রোগ্রাম (C++)

আমাদের দুটি স্ট্রিং আছে s এবং t। এই দুটি স্ট্রিং K-সদৃশ হবে যদি s-এ দুটি অক্ষরের পজিশন সোয়াপ করে ঠিক K বার করার পর ফলাফলটি t হয়। আমাদের দুটি ಅನ্যাগ্রাম s এবং t দেওয়া আছে, এবং আমাদের সবচেয়ে ছোট K বের করতে হবে যেন s এবং t K-সদৃশ হয়।

উদাহরণস্বরূপ, ইনপুট s = "abc", t = "bac" হলে আউটপুট হবে 1।

সমাধানের ধাপসমূহ (BFS)

swapp() ফাংশন ডিফাইন করুন, এটি s, i, j ইনপুট নেবে
x := s[i], y := s[j]
s[i] := y, s[j] := x
মূল মেথড থেকে নিচের কাজ করুন:
যদি A == B হয়, তবে 0 রিটার্ন করুন
visited নামে একটি সেট ডিফাইন করুন
A-কে visited-এ ইনসার্ট করুন
q নামে একটি কিউ ডিফাইন করুন, A-কে q-এ ইনসার্ট করুন
lvl := 1 দিয়ে শুরু করুন, q খালি না হওয়া পর্যন্ত, lvl ১ বাড়াতে থাকুন:
- sz := q-এর আকার
- sz নন-জিরো থাকাকালীন, প্রতিটি ইটারেশনে ১ কমানো হারে:
  - curr := q-এর প্রথম এলিমেন্ট
  - q-এ থেকে এলিমেন্ট ডিলিট করুন
  - i := 0
  - i < len(curr) এবং curr[i] == B[i] থাকাকালীন i++
  - j := i + 1 দিয়ে শুরু করুন, j < len(curr) থাকাকালীন, j++ করুন:
    - যদি curr[i] == curr[j] হয়, তবে পরবর্তী ইটারেশনে যান
    - যদি curr[j] != B[i] হয়, তবে পরবর্তী ইটারেশনে যান
    - যদি curr[j] == B[j] হয়, তবে পরবর্তী ইটারেশনে যান
    - swapp(curr, i, j)
    - যদি curr == B হয়, তবে lvl রিটার্ন করুন
    - যদি curr visited-এ না থাকে, তবে:
      - curr-কে visited-এ ইনসার্ট করুন
      - curr-কে q-এ ইনসার্ট করুন
    - swapp(curr, i, j) (ব্যাকট্র্যাক)
-1 রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

#include 
using namespace std;
class Solution {
public:
    int kSimilarity(string A, string B) {
        if (A == B) return 0;
        unordered_set visited;
        visited.insert(A);
        queue 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;
    }
};
int main(){ Solution ob; cout << (ob.kSimilarity("abc", "bac")); }

ইনপুট

"abc", "bac"