मान लीजिए हमारे पास दो स्ट्रिंग्स A और B हैं। ये दो स्ट्रिंग्स K-समान हैं (जहां K एक गैर-ऋणात्मक पूर्णांक है) यदि हम A में दो अक्षरों की स्थितियों को ठीक K बार स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग B हो जाए। तो, हमारे पास दो एनाग्राम A और B हैं, हमें सबसे छोटा K ढूंढना है जिसके लिए A और B K-समान हैं।
उदाहरण के लिए, यदि A = "abc", B = "bac", तो आउटपुट 1 होगा।
हल करने का दृष्टिकोण
हम प्रूनिंग के साथ BFS का उपयोग करते हैं:
यदि A == B, तो 0 वापस करें
विज़िटेड स्ट्रिंग्स के लिए सेट और BFS के लिए क्यू का उपयोग करें
प्रत्येक स्तर पर, सभी स्ट्रिंग्स को संसाधित करें
पहला बेमेल सूचकांक i ढूंढें
j > i के लिए स्वैप आजमाएं जहां curr[j] == B[i] और curr[j] != B[j]
यदि स्वैप के बाद B से मेल खाता है, तो स्तर वापस करें
अन्यथा, यदि विज़िट नहीं किया गया है, तो क्यू में जोड़ें
उदाहरण
#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;
swap(curr[i], curr[j]);
if (curr == B) return lvl;
if (!visited.count(curr)) {
visited.insert(curr);
q.push(curr);
}
swap(curr[i], curr[j]);
}
}
}
return -1;
}
};
int main(){
Solution ob;
cout << (ob.kSimilarity("abc", "bac"));
return 0;
}
इनपुट
"abc", "bac"
आउटपुट
1
