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