Tuyên bố vấn đề
Cho n xâu là hoán vị của nhau. Chúng ta cần làm cho tất cả các chuỗi giống nhau bằng một phép toán di chuyển ký tự đầu tiên của bất kỳ chuỗi nào đến cuối chuỗi đó.
Ví dụ
Nếu arr [] ={“abcd”, “cdab”} thì cần 2 lần di chuyển.
- Hãy để chúng tôi lấy chuỗi đầu tiên “abcd”. Di chuyển ký tự ‘a’ đến cuối chuỗi. Sau khi chuỗi hoạt động này trở thành “bcda”
- Bây giờ hãy di chuyển ký tự ‘b’ đến cuối chuỗi. Sau khi chuỗi hoạt động này trở thành “cdab”. Điều này làm cho cả hai chuỗi bằng nhau
Thuật toán
- Lấy chuỗi đầu tiên. Hãy để chúng tôi gọi nó là 'str1'.
-
Tạo một chuỗi tạm thời bằng cách nối str1 với str1 như sau -
temp =str1 + str1
- Đếm số vòng quay cần thiết để làm cho tất cả các chuỗi khác giống với mục tiêu hiện tại
- Lặp lại các bước trên cho tất cả các chuỗi và trả về giá trị tối thiểu của tất cả các số lượng.
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum moves: 2