資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學透過交換操作檢查兩個字串陣列是否相等
字串陣列是儲存字元的二維陣列。在 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 次瀏覽
廣告