คำชี้แจงปัญหา
กำหนด n สตริงที่เรียงสับเปลี่ยนกัน เราจำเป็นต้องทำให้สตริงทั้งหมดเหมือนกันด้วยการดำเนินการที่ย้ายอักขระตัวแรกของสตริงใดๆ ไปยังจุดสิ้นสุด
ตัวอย่าง
ถ้า arr[] ={“abcd”, “cdab”} จำเป็นต้องมี 2 การเคลื่อนไหว
- ให้เราใช้สตริงแรก “abcd” ย้ายอักขระ 'a' ไปที่ท้ายสตริง หลังจากที่สตริงการดำเนินการนี้กลายเป็น “bcda”
- ตอนนี้ย้ายอักขระ '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
