ข้อความโจทย์
กำหนด n สตริงที่เป็นการสลับของกันและกัน เราต้องทำให้สตริงทั้งหมดเหมือนกันด้วยการดำเนินการที่ย้ายตัวอักษรแรกของสตริงใดสตริงหนึ่งไปไว้ที่ท้ายของมัน
ตัวอย่าง
ถ้า 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
