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

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

示例示例

Input1: string str1 = “shkej”

Output: 10

Explanation

的中文翻译为：

解释

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

Input2: string str1 = “abace”

Output: 6

Explanation

的中文翻译为：

解释

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

Naive Approach

的中文翻译为：

天真的方法

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

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

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

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

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

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

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

Example

#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)。

以上是反转一个字符串所需的最小相邻交换次数的详细内容。更多信息请关注PHP中文网其他相关文章！