समस्या कथन
दो स्ट्रिंग्स 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" (str1[2] को str1[3] के साथ स्वैप किया) 2. str1 = "_baaa" (str1[0] को str1[2] के साथ स्वैप किया)
एल्गोरिदम
1. स्ट्रिंग पर साधारण ब्रेडथ फर्स्ट सर्च लागू करें और BFS के लिए उपयोग की जाने वाली क्यू का एक तत्व pair str, pos होगा जहां pos स्ट्रिंग str में _ की स्थिति है। 2. 'vis' नामक एक मैप भी बनाए रखें जो स्ट्रिंग को कुंजी के रूप में और स्ट्रिंग तक पहुंचने के लिए न्यूनतम मूव्स को मान के रूप में संग्रहीत करेगा। 3. क्यू से प्रत्येक स्ट्रिंग str के लिए, दी गई चार शर्तों के आधार पर एक नई स्ट्रिंग tmp उत्पन्न करें और vis मैप को अपडेट करें: vis[tmp] = vis[str] + 1। 4. उपरोक्त चरणों को तब तक दोहराएं जब तक क्यू खाली न हो जाए या आवश्यक स्ट्रिंग उत्पन्न न हो जाए यानी tmp == B। 5. यदि आवश्यक स्ट्रिंग उत्पन्न होती है, तो vis[str] + 1 लौटाएं जो A को B में बदलने के लिए आवश्यक न्यूनतम ऑपरेशन की संख्या है।
C++ उदाहरण
#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 = 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;
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;
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;
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;
vis[ss] = dist + 1;
q.push({ss, pp + 2});
}
swap(ss[pp], ss[pp + 2]);
}
}
return 0;
}
int main() {
string str1 = "aba_a", str2 = "_baaa";
cout << "Minimum required moves: " << transformString(str1, str2) << endl;
return 0;
}
आउटपुट
Minimum required moves: 2
