समस्या कथन
दिए गए n तार जो एक दूसरे के क्रमपरिवर्तन हैं। हमें एक ऑपरेशन के साथ सभी स्ट्रिंग्स को समान बनाने की आवश्यकता है जो किसी भी स्ट्रिंग के पहले अक्षर को उसके अंत तक ले जाती है।
उदाहरण
अगर arr[] ={"abcd", "cdab"} तो 2 चालों की आवश्यकता है।
- आइए हम पहली स्ट्रिंग "abcd" लेते हैं। वर्ण 'a' को स्ट्रिंग के अंत में ले जाएँ। इस ऑपरेशन के बाद स्ट्रिंग "बीसीडीए" बन जाती है
- अब वर्ण 'b' को स्ट्रिंग के अंत में ले जाएँ। इस ऑपरेशन के बाद स्ट्रिंग "cdab" बन जाती है। जो बदले में दोनों तारों को बराबर बनाता है
एल्गोरिदम
- पहली स्ट्रिंग लें। आइए इसे 'str1' कहते हैं।
-
str1 से str1 को निम्नानुसार जोड़कर एक अस्थायी स्ट्रिंग बनाएं -
अस्थायी =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