समस्या विवरण
n स्ट्रिंग्स दी गई हैं जो एक-दूसरे के क्रमचय हैं। हमें एक ऑपरेशन के साथ सभी स्ट्रिंग्स को समान बनाना है जो किसी भी स्ट्रिंग के पहले कैरेक्टर को उसके अंत में ले जाता है।
उदाहरण
यदि arr[] = {"abcd", "cdab"} तो 2 मूव्स आवश्यक हैं।
- पहली स्ट्रिंग "abcd" लें। कैरेक्टर 'a' को स्ट्रिंग के अंत में ले जाएं। इस ऑपरेशन के बाद स्ट्रिंग "bcda" बन जाती है
- अब कैरेक्टर 'b' को स्ट्रिंग के अंत में ले जाएं। इस ऑपरेशन के बाद स्ट्रिंग "cdab" बन जाती है। जो बदले में दोनों स्ट्रिंग्स को समान बना देता है
एल्गोरिदम
- पहली स्ट्रिंग लें। आइए इसे 'str1' कहें।
str1 को str1 के साथ जोड़कर एक टेम्प स्ट्रिंग बनाएं:
temp = str1 + str1
- वर्तमान टारगेट के समान अन्य सभी स्ट्रिंग्स बनाने के लिए आवश्यक रोटेशन गिनें
- उपरोक्त चरणों को सभी स्ट्रिंग्स के लिए दोहराएं और सभी गिनतियों का न्यूनतम लौटाएं।
उदाहरण
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minMoves(string str[], int n) {
int minCnt = INT_MAX;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
string temp = str[j] + str[j];
int index = temp.find(str[i]);
if (index != string::npos) {
cnt += index;
}
}
minCnt = min(cnt, minCnt);
}
return minCnt;
}
int main() {
string str[] = {"abcd", "cdab", "bacd", "cdba"};
cout << "Minimum moves: " << minMoves(str, SIZE(str)) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है:
Minimum moves: 2
