C++ 检查两个字符串数组是否相等通过执行交换操作

字符串数组是一个存储字符的二维数组。在C++语言中，我们有一个内置函数，语法如下：

swap (first_datatype, second_datatype)

进行交换操作的目的是交换两个元素，即交换它们所携带的值。在接下来的内容中，我们还需要对字符串的元素位置进行一些交换以获得预期的输出。然而，我们可以以更简单的方式获得输出。

问题描述

现在，对于这个问题，我们提供了两个字符串数组（意思是字符串数组或者字符数组而不是数字）。我们需要通过频繁地在任意2维数组的字符串上进行交换操作来检查是否可以使得这两个字符串数组相等。接下来我们来看看应该如何解决这个问题。

示例

让我们通过一些示例来理解这个问题。

输入： –

s1 = {"aachg", "klsm", "abcd",  }
s2 = { "aghca", "dbca", "mlks"}

输出 −

true

解释 − 若我们交换第二个’a’和’g’，然后交换’c’和’h’，第一个字符串数组array1可以还原为“aghca”

若我们交换’m’和’s’，然后交换’s’和’k’，第二个字符串数组array1可以转换为“mlks”

若我们交换’d’和’a’，第三个字符串数组array1可以转换为“dbca”

因此，若我们进行所有这些交换操作，set 1中的数组元素将与set 2中的数组元素相同。尽管在两个数组中字符串的顺序或位置可能会有所不同，但会被认为存在相等的字符串元素。

输入 −

s1 = { "bbs", "aaa", “jsk” }
s2 = { "aaa", "dbs", “kjs” }

输出 –

false

解释 − 通过任意数量的字符串交换操作，无法使得给定的两个字符串相等。

问题解释

让我们试着理解这个问题并找到它的解决方法。如果我们想要判断一些交换操作是否可以使一个字符串等于另一个字符串，且对交换操作的数量没有约束，我们可以通过一种更简单的方式得到答案。我们可以首先对每个数组的字符串进行排序，然后如果我们还对两个数组进行排序，我们可以比较两个数组的相应字符串，如果每个字符串都等于其他相应字符串，那么我们可以说我们可以通过执行交换操作使这两个字符串数组相等。

解决方法

定义上述解决方法的算法

检查两个字符串的大小，如果它们的大小不相等，则无法使这两个数组的字符串相等。
同时对数组1和数组2的字符串进行排序。
同时对两个数组进行排序。
现在，如果这两个数组的字符串可以相等，它们将位于彼此的对应位置。
检查排序后的数组1中的每个字符串是否与数组2的相应位置处的字符串相同，如果是，则返回true，否则返回false。

示例：C++代码实现

#include <bits/stdc++.h>
using namespace std;
// Helper function to check if we can make the two arrays equal by performing swap operations on any of the two arrays
bool Helper(vector<string> s1, vector<string> s2){
   // If the size of both array sets is not the same we would return false right away as there is no way that we can make all the strings equal
    if(s1.size() != s2.size()){
      return false;
    }
    // Store the length of the string
    int n = s1.size();
    // start a loop to sort each string of both arrays
    for(int i=0; i < n; i++){
       // sort string present at index i of the array of set 1
       sort(s1[i].begin(),s1[i].end());
       // sort string present at index i of the array of set 2
       sort(s2[i].begin(), s2[i].end());
    }
    // Sort both arrays now so that we can compare the strings directly to ease our process
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    // Start a loop to compare each string present in the two arrays
    for (int i = 0; i < n; i++){
       // check if any string in set 1 is not equal to the corresponding string of set 2 after sorting, then there is no possible way to make both arrays equal
        if (s1[i] != s2[i]){
           return false;
        }
    }
    // Return true if every single string of set 1 is equal to every corresponding string of set 2
    return true;
}
// Main function
int main(){
    vector<string> s1 = {"aachg", "klsm", "abcd"};
    vector<string> s2 = { "aghca", "dbca", "mlks"};
    // Call the Helper function to get a binary answer true (1) or false (0) based on which we would deliver our final output
    bool output = Helper(s1, s2);
    if(output==0){
       cout<< "False: Not every single string of set 1 is equal to every other string of set 2" << endl;
    }
    else{
       cout<< "True: Every single string of set 1 is equal to every other string of set 2" << endl;
    }
    return 0;
}

输出

True: Every single string of set 1 is equal to every other string of set 2

上述代码的复杂性

时间复杂度 – O(n*log(n)); 其中n是数组的大小，由于我们在这里使用了排序，并且我们知道内置函数’sort’的时间复杂度是n*log(n)
空间复杂度 – O(1); 在上述代码中我们没有存储任何变量在某个数据结构中。

结论

在本文中，我们通过执行交换操作来检查两个字符串数组是否相等。首先，我们观察到我们对达到目标所需的交换次数没有任何限制。我们将利用这一事实，使得问题在我们对每个数组的字符串进行排序后更容易一些，可以使得两个字符串数组通过执行交换操作相等。如果我们已经对两个数组进行了排序，我们可以比较两个数组中对应的字符串，并得出结论。