সমস্যা বিবরণ
nটি স্ট্রিং দেওয়া আছে যা একে অপরের পারমিউটেশন। আমাদের সব স্ট্রিংকে সমান করতে হবে একটি অপারেশন দিয়ে যেটি যেকোনো স্ট্রিং-এর ফার্স্ট ক্যারেক্টারকে এন্ডে মুভ করে।
উদাহরণ
যদি arr[] = {"abcd", "cdab"} হয়, তবে ২ মুভ দরকার।
- প্রথম স্ট্রিং "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
