最小移动到结束操作以使所有字符串在C ++中相等

问题陈述

给定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