每个字符串都是由按顺序排列的字符序列组成的。该字符串可以由字母、数字甚至特殊字符组成。
任何输入字符串的字谜词是具有随机字符排列的字符串。这意味着，当重新排列字符的顺序时，就获得了字符串的字谜词。在字谜中，字符各自的数量也应该保持相同。两个字谜字符串具有以下含义 -
它们都包含相同的字符集。
它们都可能有不同的字符排列
例如，feed 和 def 不是彼此的字谜词，因为第一个字符串中的字符“e”重复了两次。
相邻字符是字符串中相邻位置的字母。
为了使字符串相等，两个字符串的相应字符必须匹配。
问题陈述是首先检查给定的两个字符串是否是彼此的字谜词，如果是，则返回获得相等的字谜字符串所需的最小交换次数。
说明问题陈述的一些示例如下 -
示例示例
示例 1 - str1：“abca”
str2：“巴克”
输出：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)，本质上是常数。
