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


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

语法

swap (first_datatype, second_datatype)

用于对两个元素执行交换操作,即交换它们的值。在下面,我们还应该对字符串元素的位置进行一些交换以获得预期的输出。但是,我们可以通过更简单的方法获得输出。

问题陈述

现在,在这个问题中,我们得到了两个字符串数组(意味着字符数组而不是数字数组)。我们必须检查是否可以通过对任何一个二维数组的字符串频繁执行交换操作来使字符串数组相等。让我们看看我们应该如何解决这个问题。

示例

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

输入

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

输出

true

解释 − 如果我们交换第二个 'a' 和 'g',然后交换 'c' 和 'h',则第一个字符串数组1可以交换回“aghca”。

数组1的第二个字符串可以通过交换 'm' 和 's',然后交换 's' 和 'k' 来转换为“mlks”。

数组1的第三个字符串可以通过交换 'd' 和 'a' 来转换为“dbca”。

因此,如果我们执行所有这些交换操作,我们将使集合1的数组元素与集合2中的所有数组元素相同。尽管两个数组中字符串的顺序或位置可能不同,但它将被认为具有所需的相等字符串元素。

输入

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

输出

false

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

问题解释

让我们尝试理解问题并找到解决方案。如果我们想查看一些交换操作是否可以使一个字符串等于另一个字符串,并且对我们可以执行的交换操作次数没有限制,我们可以通过更简单的方法得到答案。我们可以首先对每个数组的每个字符串进行排序,然后如果我们也对这两个数组进行排序,我们可以比较两个数组的对应字符串,如果每个字符串都等于每个其他对应字符串,那么我们可以说我们可以通过执行交换操作来使两个字符串数组相等。

解决方案

上述解决方案的算法

  • 检查两个字符串的大小,如果它们的大小不相等,则无法使两个数组的字符串相等。

  • 同时对数组1和数组2的字符串进行排序。

  • 也对这两个数组进行排序。

  • 现在,如果两个数组的字符串可以相等,它们将位于彼此对应的位 置。

  • 检查排序后的数组1中的每个字符串是否与数组2中对应位置的字符串相同;如果相同则返回true,否则返回false。

示例

现在,让我们在不同的编程语言中实现上述方法:C++、Java 和 Python −

#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
import java.util.Arrays;
public class Main {
   // Helper function to check if we can make the two arrays equal by performing swap operations on any of the two arrays
   public static boolean helper(String[] s1, String[] s2) {
      // If the sizes of both arrays are not the same, return false immediately as there's no way to make them equal
      if (s1.length != s2.length) {
         return false;
      }

      int n = s1.length; // Store the length of the arrays

      // Sort each string in both arrays
      for (int i = 0; i < n; i++) {
         char[] s1Chars = s1[i].toCharArray();
         char[] s2Chars = s2[i].toCharArray();
         Arrays.sort(s1Chars);
         Arrays.sort(s2Chars);
         s1[i] = new String(s1Chars);
         s2[i] = new String(s2Chars);
      }

      // Sort both arrays to compare the strings directly
      Arrays.sort(s1);
      Arrays.sort(s2);

      // Compare each string in the two arrays
      for (int i = 0; i < n; i++) {
         // If any string in s1 is not equal to the corresponding string in s2 after sorting, there's no way to make both arrays equal
         if (!s1[i].equals(s2[i])) {
            return false;
         }
      }
      // Return true if every string in s1 is equal to the corresponding string in s2
      return true;
   }
   // Main function
   public static void main(String[] args) {
      String[] s1 = {"aachg", "klsm", "abcd"};
      String[] s2 = {"aghca", "dbca", "mlks"};

      // Call the helper function to get a binary answer: true or false
      boolean output = helper(s1, s2);
      if (!output) {
         System.out.println("False: Not every single string of set 1 is equal to every other string of set 2");
      } else {
         System.out.println("True: Every single string of set 1 is equal to every other string of set 2");
      }
   }
}

输出

True: Every single string of set 1 is equal to every other string of set 2
def helper(s1, s2):
   # If the sizes of both lists are not the same, return False immediately as there's no way to make them equal
   if len(s1) != len(s2):
      return False
    
   n = len(s1)  # Store the length of the lists
   # Sort each string in both lists
   for i in range(n):
      s1[i] = ''.join(sorted(s1[i]))
      s2[i] = ''.join(sorted(s2[i]))
    
   # Sort both lists to compare the strings directly
   s1.sort()
   s2.sort()
    
   # Compare each string in the two lists
   for i in range(n):
      # If any string in s1 is not equal to the corresponding string in s2 after sorting, there's no way to make both lists equal
      if s1[i] != s2[i]:
         return False
    
   # Return True if every string in s1 is equal to the corresponding string in s2
   return True

# Main function
def main():
   s1 = ["aachg", "klsm", "abcd"]
   s2 = ["aghca", "dbca", "mlks"]
    
   # Call the helper function to get a binary answer: True (1) or False (0)
   output = helper(s1, s2)
    
   if output == 0:
      print("False: Not every single string of set 1 is equal to every other string of set 2")
   else:
      print("True: Every single string of set 1 is equal to every other string of set 2")

if __name__ == "__main__":
   main()

输出

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);我们在上述代码中没有在任何数据结构中存储任何变量。

结论

在本文中,为了检查两个字符串数组是否可以通过交换操作相等,我们将首先观察到我们对必须进行的交换次数没有任何限制。我们将利用这一事实使我们的问题更简单一些,如果我们取两个字符串数组,则在对每个数组中的各个字符串进行排序后,可以通过交换操作使它们相等。如果我们也对这两个数组进行了排序,我们可以比较两个数组中对应的字符串,并得出结论。

更新于:2024年1月22日

211 次浏览

开启你的职业生涯

完成课程后获得认证

开始学习
广告