将字符串转换为其给定异位词所需的相邻交换最小次数

---

每个字符串都是由按顺序排列的一系列字符组成的。字符串可以由字母、数字甚至特殊字符组成。

任何输入字符串的异位词都是字符随机排列的字符串。这意味着，当字符的顺序重新排列时，就会得到字符串的异位词。异位词中字符的各自计数也应该保持相同。两个异位词字符串具有以下含义：

• 它们都包含相同的字符集。

• 它们可能有不同的字符排列。

例如，“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)，本质上是常数。