C++ 中使所有字符串相等所需的最小移动次数

问题陈述

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

更新于: 2019-11-22

351 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告