Đề bài
Cho n chuỗi là hoán vị của nhau. Cần làm cho tất cả chuỗi giống nhau bằng phép toán di chuyển ký tự đầu tiên của chuỗi bất kỳ ra cuối chuỗi đó.
Ví dụ
Nếu arr[] = {"abcd", "cdab"} thì cần 2 phép di chuyển.
- Lấy chuỗi đầu tiên "abcd". Di chuyển 'a' ra cuối → "bcda"
- Di chuyển 'b' ra cuối → "cdab". Lúc này hai chuỗi bằng nhau.
Thuật toán
- Lấy chuỗi đầu tiên, gọi là 'str1'.
- Tạo chuỗi tạm bằng cách nối str1 với str1: temp = str1 + str1
- Đếm số vòng xoay cần để các chuỗi khác giống chuỗi mục tiêu hiện tại.
- Lặp lại cho tất cả chuỗi và trả về giá trị nhỏ nhất.
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 << "Số phép di chuyển tối thiểu: " << minMoves(str, SIZE(str)) << endl;
return 0;
}
Kết quả
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:
Số phép di chuyển tối thiểu: 2