ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে। এই দুটি স্ট্রিং K- অনুরূপ যখন আমরা s ঠিক K সময়ে দুটি অক্ষরের অবস্থান অদলবদল করতে পারি যাতে ফলস্বরূপ স্ট্রিং টি হয়। আমাদের দুটি অ্যানাগ্রাম s এবং t আছে, এবং আমাদের সবচেয়ে ছোট K খুঁজে বের করতে হবে যার জন্য s এবং t K- অনুরূপ।
সুতরাং, যদি ইনপুট s ="abc", t ="bac" এর মত হয়, তাহলে আউটপুট হবে 1।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন 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 অ-শূন্য হয়, প্রতিটি পুনরাবৃত্তিতে sz 1 দ্বারা হ্রাস করুন, করুন:
-
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"
আউটপুট
1
