C++ 反转字符串所需的最小相邻交换次数

给定一个字符串str，我们只能交换相邻字符来使字符串反转。我们需要找到使字符串反转所需的最小移动次数，仅通过交换相邻字符来实现。我们将实现两种方法来找到所需的解决方案，并给出代码的解释和实现。

示例

Input1: string str1 = “shkej”

Output: 10

解释

首先，我们将最后一个字符移到第一个位置，这需要4次交换，字符串将变为“jshke”。然后我们将‘e’移到第二个位置，这需要3次交换。同样地，对于‘k’，我们需要两次交换，而对于‘h’只需要1次交换，最终答案是10。

Input2: string str1 = “abace”

Output: 6

解释

首先，我们将交换第二个索引处的字符，将其移到最后一个索引处需要两次交换，字符串将变为“abcea”。然后我们将’b’交换为’e’需要两次交换，字符串将变为“aceba”。然后再进行两次交换，得到最终的反向字符串，总共需要进行6次交换。

原生方法

我们已经看过了上面的示例，现在让我们来看看实现正确代码所需的步骤。

• 首先，我们将创建一个函数，该函数将以给定的字符串作为参数，并将返回所需的最小步骤数作为返回值。

• 在函数中，我们将创建字符串的副本，然后将其反转以与原始字符串进行比较。

• 我们将创建三个变量，前两个用于对字符串进行遍历，最后一个用于存储所需的步骤数。

• 通过使用while循环，我们将遍历给定的字符串，并继续跳过当前索引值与反向字符串相同的迭代次数。

• 然后，我们将使用while循环交换相邻的字符，直到’j’到达’i’，并在每次交换时增加计数。

• 最后，我们将返回计数的值，并在主函数中打印出来。

示例

#include <bits/stdc++.h>
using namespace std;
// function to get the minimum number of swaps 
int minSwaps(string str){
   string temp = str;
   reverse(temp.begin(), temp.end()); // reversing the string 
   int i = 0, j = 0;
   int ans = 0;
   int len = str.size();
   while (i <len) {
      j = i;        
      // find the character that is equal to the current element 
      while (str[j] != temp[i]) {
         j++;
      }
      // iterating util the current i is equal to j
      while (i < j) {
         char tempc = str[j];
         str[j] = str[j - 1];
         str[j - 1] = tempc;
         j--;
         ans++;
      }
      i++;
   }
   return ans;
}
int main(){
   string str = "efabc"; // given string     
   // calling the function to find the minimum number of steps required 
   cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
   return 0;
}

输出

The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10

时间和空间复杂度

上述代码的时间复杂度为O(N^2)，其中N是给定字符串的长度。我们使用嵌套的while循环在迭代中得到了N的因子。

上述代码的空间复杂度为O(N)，因为我们在那里创建了一个额外的字符串来存储给定字符串的反转。

注意 − 这里可以实施另一种方法，但需要使用非常先进的数据结构。该方法背后的概念是，我们可以从最后一个字符开始，直到第一个字符相遇。然后，我们可以理论上将该字符移动到最后一个位置，并将该位置标记为达成，并将该值存储在高级数据结构中。

然后，类似地，对于每个字符，我们将找到从后面出现的相同字符，该字符没有被标记，然后增加计数器，该计数器为它后面的元素数量减去已标记的元素数量。

结论

在本教程中，我们实现了一个代码来通过只交换相邻字符来找到反转给定字符串所需的最少步骤数。我们使用嵌套的while循环和反转给定字符串的副本来找到解决方案。上述代码的时间复杂度为O(N^2)，其中N是字符串的大小，空间复杂度为O(N)。