समस्या कथन
दो स्ट्रिंग्स str1 और str2 को देखते हुए, दोनों स्ट्रिंग्स में 'a' और 'b' अक्षर होते हैं। दोनों तार समान लंबाई के हैं। दोनों स्ट्रिंग्स में एक _ (रिक्त स्थान) है। कार्य निम्न कार्यों की न्यूनतम संख्या करके पहली स्ट्रिंग को दूसरी स्ट्रिंग में परिवर्तित करना है -
-
यदि _ स्थिति I पर है तो _ को i+1 या i-1 की स्थिति वाले वर्ण से बदला जा सकता है
-
यदि स्थिति i+1 और i+2 पर वर्ण भिन्न हैं तो _ को i+1 या i+2 स्थिति वाले वर्ण से बदला जा सकता है
-
इसी तरह, यदि स्थिति i-1 और i-2 पर वर्ण भिन्न हैं तो _ को i-1 या i-2 स्थिति वाले वर्ण से बदला जा सकता है
अगर str1 ="aba_a" और str2 ="_baaa" तो हमें str1 को str2 में बदलने के लिए 2 चालों की आवश्यकता होती है -
1. str1 = “ab_aa” (Swapped str1[2] with str1[3]) 2. str2 = “_baaa” (Swapped str1[0] with str1[2])
एल्गोरिदम
1. Apply a simple Breadth First Search over the string and an element of the queue used for BFS will contain the pair str, pos where pos is the position of _ in the string str. 2. Also maintain a map namely ‘vis’ which will store the string as key and the minimum moves to get to the string as value. 3. For every string str from the queue, generate a new string tmp based on the four conditions given and update the vis map as vis[tmp] = vis[str] + 1. 4. Repeat the above steps until the queue is empty or the required string is generated i.e. tmp == B 5. If the required string is generated, then return vis[str] + 1 which is the minimum number of operations required to change A to B.
उदाहरण
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int transformString(string str, string f){
unordered_map<string, int> vis;
int n;
n = str.length();
int pos = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '_') {
pos = i;
break;
}
}
queue<pair<string, int> > q;
q.push({ str, pos });
vis[str] = 0;
while (!q.empty()) {
string ss = q.front().first;
int pp = q.front().second;
int dist = vis[ss];
q.pop();
if (pp > 0) {
swap(ss[pp], ss[pp - 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 1 });
}
swap(ss[pp], ss[pp - 1]);
}
if (pp < n - 1) {
swap(ss[pp], ss[pp + 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 1 });
}
swap(ss[pp], ss[pp + 1]);
}
if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
swap(ss[pp], ss[pp - 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 2 });
}
swap(ss[pp], ss[pp - 2]);
}
if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
swap(ss[pp], ss[pp + 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 2 });
}
swap(ss[pp], ss[pp + 2]);
}
}
return 0;
}
int main(){
string str1 = "aba_a";
string str2 = "_baaa";
cout << "Minimum required moves: " << transformString(str1, str2) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -
Minimum required moves: 2