मान लीजिए कि हमारे पास दो तार s और t हैं। ये दो तार K-समान हैं जब हम दो अक्षरों की स्थिति को s ठीक K बार में स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग t हो। हमारे पास दो विपर्यय s और t हैं, और हमें सबसे छोटा K ज्ञात करना है जिसके लिए s और t K-समान हैं।
इसलिए, यदि इनपुट s ="abc", t ="bac" जैसा है, तो आउटपुट 1 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन स्वैप () को परिभाषित करें, यह स्ट्रिंग s, i, j,
लेगा -
एक्स:=एस[i], वाई:=एस[जे]
-
s[i] :=y, s[j] :=x
-
मुख्य विधि से निम्न कार्य करें -
-
अगर ए, बी के समान है, तो:, 0 लौटाएं
-
देखे गए एक सेट को परिभाषित करें
-
विज़िट किए गए में A डालें
-
एक कतार q को परिभाषित करें, A को q में डालें
-
lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -
-
sz :=q का आकार
-
जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz को 1 से घटाएं, करें:
-
curr :=q का पहला तत्व
-
q से तत्व हटाएं
-
मैं :=0
-
जबकि (i
-
(मैं 1 से बढ़ाइए)
-
-
इनिशियलाइज़ j :=i + 1 के लिए, जब j
-
अगर curr[i], curr[j] के समान है, तो:
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
अगर curr[j] B[i] के बराबर नहीं है, तो:
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
अगर curr[j] B[j] के समान है, तो:
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
स्वैप (करंट, आई, जे)
-
अगर curr B के समान है, तो:
-
वापसी एलवीएल
-
-
यदि विज़िट की गई कॉल काउंट (कर) नहीं है, तो:
-
विज़िट किए गए में curr डालें
-
क्यू में कर्व डालें
-
-
स्वैप (करंट, आई, जे)
-
-
-
-
वापसी -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