সমস্যা বিবৃতি
দেওয়া n স্ট্রিং যে একে অপরের permutations হয়. আমাদের একটি অপারেশনের মাধ্যমে সমস্ত স্ট্রিংকে একই রকম করতে হবে যা যেকোনো স্ট্রিংয়ের প্রথম অক্ষরটিকে এর শেষে নিয়ে যায়।
উদাহরণ
যদি 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
