C++程序 将所有字符串变成相等的操作的最小操作次数
给定n个字符串,它们是彼此的排列。我们需要通过一个操作使所有字符串相同,该操作将任何字符串的前字符移到末尾。
示例:
输入:n = 2
arr[] = {"molzv", "lzvmo"}
输出:2
解释:在第一个字符串中,我们将第一个元素(“m”)从第一个字符串中移除并将其追加到末尾。然后我们移动第一个字符串的第二个字符并将其移到末尾。所以经过2次操作,两个字符串变得相同。
输入:n = 3
arr[] = {"kc", "kc", "kc"}
输出:0
解释:已经所有的字符串都是相等的。
将末尾到操作基本上是左旋。我们使用“检查字符串是否彼此旋转”中讨论的方法来计算使两个字符串相同所需的迁移到前面操作的数量。我们一个一个地将每个字符串作为目标字符串。我们计算旋转次数,以使所有其他字符串与当前目标相同,并最后返回所有计数的最小值。
下面是上述方法的实现。
// CPP program to make all strings same using
// move to end operations.
#include <bits/stdc++.h>
using namespace std;
// Returns minimum number of moves to end
// operations to make all strings same.
int minimunMoves(string arr[], int n)
{
int ans = INT_MAX;
for (int i = 0; i < n; i++)
{
int curr_count = 0;
// Consider s[i] as target string and
// count rotations required to make
// all other strings same as str[i].
for (int j = 0; j < n; j++) {
string tmp = arr[j] + arr[j];
// find function returns the index where we
// found arr[i] which is actually count of
// move-to-front operations.
int index = tmp.find(arr[i]);
// If any two strings are not rotations of
// each other, we can't make them same.
if (index == string::npos)
return -1;
curr_count += index;
}
ans = min(curr_count, ans);
}
return ans;
}
// driver code for above function.
int main()
{
string arr[] = {"xzzwo", "zwoxz", "zzwox", "xzzwo"};
int n = sizeof(arr)/sizeof(arr[0]);
cout << minimunMoves(arr, n);
return 0;
}
输出:
5
时间复杂度: O(N 3 )(由于使用了两个嵌套循环,N是内部for循环中使用的find()函数)
空间复杂度 : O(1)因为使用常量变量