मान लीजिए कि हमारे पास दो तार ए और बी हैं। ये दो तार के-समान हैं (जहां के एक गैर-ऋणात्मक पूर्णांक है) यदि हम दो अक्षरों की स्थिति को ए में बिल्कुल के समय में स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग बी हो। तो, हमारे पास है दो विपर्यय A और B, हमें सबसे छोटा K ज्ञात करना है जिसके लिए A और B K-समान हैं।
इसलिए, यदि इनपुट A ="abc", B ="bac" जैसा है, तो आउटपुट 2 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन स्वैप () को परिभाषित करें, यह स्ट्रिंग 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
