反轉一個字串所需的最小相鄰交換次數

給定一個字串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中文網其他相關文章！