將字串轉換為其給定異位詞所需的相鄰交換最小次數


每個字串都是由按順序排列的一系列字元組成的。字串可以由字母、數字甚至特殊字元組成。

任何輸入字串的異位詞都是字元隨機排列的字串。這意味著,當字元的順序重新排列時,就會得到字串的異位詞。異位詞中字元的各自計數也應該保持相同。兩個異位詞字串具有以下含義:

  • 它們都包含相同的字元集。

  • 它們可能有不同的字元排列。

例如,“feed”和“def”彼此不是異位詞,因為第一個字串中的字元“e”重複了兩次。

相鄰字元是字串中相鄰位置的字母。

為了使字串相等,必須匹配兩個字串的對應字元。

問題陳述是首先檢查給定的兩個字串是否彼此是異位詞,如果是,則返回獲得相等異位詞字串所需的最小交換次數。

一些說明問題陳述的示例如下:

示例

示例 1 - str1:“abca”

str2:“baac”

輸出:2

解釋:以下字串彼此是異位詞,並且可以透過執行以下兩個交換將 str1 轉換為 str2:

swap(0,1) 生成“baca”

swap(2,3) 生成“baac”

示例 2 - str1:“aaf”

str2:“faa”

解釋:2

最初,執行 swap(2,3) 以生成“afa”

然後,執行 swap(1,2) 以生成“faa”

此問題可以透過使用字元檢查的概念以及使用 STL 內建方法來解決:

sort() 對字串進行排序

swap(i,j) 分別交換第 i 個和第 j 個索引位置處的字元。

演算法

  • 步驟 1 - 使用 sort() 方法對提供的兩個字串 str1 和 str2 進行排序。

  • 步驟 2 - 分別比較它們的字元以檢查兩個字串在本質上是否等效。

  • 步驟 3 - 如果兩個排序後的字串等效,則它們彼此是異位詞。

  • 步驟 4 - 維持一個計數器以跟蹤到目前為止執行的交換次數。

  • 步驟 5 - 初始化兩個指標 i 和 j,並將第二個字串的指標遞增,直到第一個字串的第 i 個索引處的字元和第二個字串的第 j 個索引處的字元匹配,使得 str1[i] = str2[j]。

  • 步驟 6 - 為了匹配相等字元的位置,使用 swap() 函式交換相鄰元素以及索引 j 和 j-1。

  • 步驟 7 - 然後將 j 計數器遞減,直到它等於 i。

  • 步驟 8 - 現在遞增 i 指標。

  • 步驟 9 - 此過程一直持續到整個長度耗盡。

示例

以下 C++ 程式碼片段以兩個字串作為輸入,並找出這兩個字串是否彼此是異位詞以及將它們轉換為等效字串所需的最小交換次數。

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//check whether the two input strings are anagram of each other or not
bool checkanagram(string s1, string s2) {

   //sorting the strings to check the equivalence of strings after sorting
   sort(s1.begin(), s1.end());
   sort(s2.begin(), s2.end());

   //checking if all the characters occur in order
   if (s1 == s2)
      return true;
   else
      return false;
}

// Function to return the minimum swaps required
int minSwaps(string str1, string str2) {

   //initialising the pointers
   int i = 0, j = 0;

   //initialising minswaps with 0
   int minswaps = 0;
   int len = str1.length();

   //changing the characters of str1 to be equivalent to str2
   for(i=0; i < len;i++) {

      //initialising the second pointer at the first one
      j = i;

      //computing the index element where jth index of first string is equivalent to ith index of second string
      while (str1[j] != str2[i]) {
         j += 1;
      }

      //equalising element available at the ith position
      while (i < j) {

         //swapping adjacent elements available at the j and j-1 positions respectively
         swap(str1[j],str1[j-1]);

         //increasing the number of swaps each time
         minswaps += 1;
         j--;
      }
   }
   return minswaps;
}

//calling the method to simulate minimum swaps for conversion of strings
int main() {

   //declaring both the strings
   string str1 = "male";
   string str2 = "lame";

   //check if both the strings are anagram of each other
   bool anares = checkanagram(str1,str2);
   if(anares){
      int swaps = minSwaps(str1,str2);
      cout<<"Minimum no of swaps to convert string1 to string2 : "<<swaps;
   }
   else
      cout << "Strings are not anagram of each other.";
   return 0;
}

輸出

Minimum no of swaps to convert string1 to string2 : 3

結論

異位詞字串只是同一字元集的不同排列。只需交換對應位置的字元即可使它們相似。

上述方法的時間複雜度為 O(n*n),其中 n 是字串的長度。這是因為在第一個字串中的每個索引字元都在第二個字串的整個長度中搜索。

上述指定演算法的空間複雜度為 O(1),本質上是常數。

更新於: 2023年3月15日

632 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告