資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查陣列中所有字串是否可以透過交換字元使其相同
在本文中，我們將探討檢查陣列中所有字串是否可以透過交換字元使其相同的問題。我們將首先理解問題陳述，然後研究解決此問題的簡單方法和高效方法，以及它們各自的演算法和時間複雜度。最後，我們將用C++實現解決方案。
問題陳述
給定一個字串陣列，確定所有字串是否可以透過交換字元使其相同。
簡單方法
簡單的方法是將陣列中每個字串的字元排序，然後將每個排序後的字串與下一個排序後的字串進行比較。如果所有排序後的字串都相等，則意味著所有字串都可以透過交換字元使其相同。
演算法（簡單）
對陣列中每個字串的字元進行排序。
將每個排序後的字串與下一個排序後的字串進行比較。
如果所有排序後的字串都相等，則返回true；否則，返回false。
程式碼（簡單）
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// Function to check if all strings can be made the same by interchanging characters
bool canBeMadeSame(char strArray[][4], size_t size) {
// Iterate through each string in the array
for (size_t i = 0; i < size; i++) {
size_t len = strlen(strArray[i]);
// Sort the characters within the current string
for (size_t j = 1; j < len; j++) {
for (size_t k = 0; k < len - j; k++) {
if (strArray[i][k] > strArray[i][k + 1]) {
char temp = strArray[i][k];
strArray[i][k] = strArray[i][k + 1];
strArray[i][k + 1] = temp;
}
}
}
}
// Check if all sorted strings are the same
for (size_t i = 1; i < size; i++) {
if (strcmp(strArray[i - 1], strArray[i]) != 0) {
return false;
}
}
return true;
}
int main() {
char strArray[][4] = {"abb", "bba", "bab"};
size_t size = sizeof(strArray) / sizeof(strArray[0]);
// Check if all strings can be made the same by interchanging characters
if (canBeMadeSame(strArray, size)) {
printf("All strings can be made the same by interchanging characters.\n");
} else {
printf("All strings cannot be made the same by interchanging characters.\n");
}
return 0;
}
輸出
All strings can be made the same by interchanging characters.
#include <iostream>
#include <vector>
#include <algorithm>
bool canBeMadeSame(std::vector<std::string> &strArray) {
for (auto &str : strArray) {
std::sort(str.begin(), str.end());
}
for (size_t i = 1; i < strArray.size(); i++) {
if (strArray[i - 1] != strArray[i]) {
return false;
}
}
return true;
}
int main() {
std::vector<std::string> strArray = {"abb", "bba", "bab"};
if (canBeMadeSame(strArray)) {
std::cout << "All strings can be made the same by interchanging characters." << std::endl;
} else {
std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
}
return 0;
}
輸出
All strings can be made the same by interchanging characters.
import java.util.Arrays;
public class Main {
public static boolean canBeMadeSame(String[] strArray) {
// Sort the characters within each string
for (int i = 0; i < strArray.length; i++) {
char[] arr = strArray[i].toCharArray();
Arrays.sort(arr);
strArray[i] = new String(arr);
}
// Check if all sorted strings are the same
for (int i = 1; i < strArray.length; i++) {
if (!strArray[i - 1].equals(strArray[i])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] strArray = {"abb", "bba", "bab"};
// Check if all strings can be made the same by interchanging characters
if (canBeMadeSame(strArray)) {
System.out.println("All strings can be made the same by interchanging characters.");
} else {
System.out.println("All strings cannot be made the same by interchanging characters.");
}
}
}
輸出
All strings can be made the same by interchanging characters.
def can_be_made_same(str_array):
# Sort the characters within each string
for i in range(len(str_array)):
str_array[i] = ''.join(sorted(str_array[i]))
# Check if all sorted strings are the same
for i in range(1, len(str_array)):
if str_array[i - 1] != str_array[i]:
return False
return True
str_array = ["abb", "bba", "bab"]
# Check if all strings can be made the same by interchanging characters
if can_be_made_same(str_array):
print("All strings can be made the same by interchanging characters.")
else:
print("All strings cannot be made the same by interchanging characters.")
輸出
All strings can be made the same by interchanging characters.
時間複雜度（簡單）：O(n * m * log(m))，其中n是陣列中字串的數量，m是陣列中字串的最大長度。
高效方法
高效的方法是計算每個字串中每個字元的頻率並將計數儲存在頻率陣列中。然後，比較所有字串的頻率陣列。如果它們相等，則意味著所有字串都可以透過交換字元使其相同。
演算法（高效）
為陣列中的每個字串初始化一個頻率陣列向量。
計算每個字串中每個字元的頻率，並將其儲存在相應的頻率陣列中。
比較所有字串的頻率陣列。
如果所有頻率陣列都相等，則返回true；否則，返回false。
程式碼（高效）
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool canBeMadeSame(char strArray[][4], size_t size) {
int freqArrays[size][26]; // Create a 2D array for frequency counts
// Initialize the frequency arrays with zeros
for (size_t i = 0; i < size; i++) {
for (int j = 0; j < 26; j++) {
freqArrays[i][j] = 0;
}
}
// Count the frequency of each character in each string
for (size_t i = 0; i < size; i++) {
for (size_t j = 0; j < strlen(strArray[i]); j++) {
freqArrays[i][strArray[i][j] - 'a']++;
}
}
// Check if frequency arrays of all strings are the same
for (size_t i = 1; i < size; i++) {
for (int j = 0; j < 26; j++) {
if (freqArrays[i - 1][j] != freqArrays[i][j]) {
return false;
}
}
}
return true;
}
int main() {
char strArray[][4] = {"abb", "bba", "bab"};
size_t size = sizeof(strArray) / sizeof(strArray[0]);
if (canBeMadeSame(strArray, size)) {
printf("All strings can be made the same by interchanging characters.\n");
} else {
printf("All strings cannot be made the same by interchanging characters.\n");
}
return 0;
}
輸出
All strings can be made the same by interchanging characters.
#include <iostream>
#include <vector>
#include <algorithm>
bool canBeMadeSame(std::vector<std::string> &strArray) {
std::vector<std::vector<int>> freqArrays(strArray.size(), std::vector<int>(26, 0));
for (size_t i = 0; i < strArray.size(); i++) {
for (char ch : strArray[i]) {
freqArrays[i][ch - 'a']++;
}
}
for (size_t i = 1; i < freqArrays.size(); i++) {
if (freqArrays[i - 1] != freqArrays[i])
return false;
}
return true;
}
int main() {
std::vector<std::string> strArray = {"abb", "bba", "bab"};
if (canBeMadeSame(strArray)) {
std::cout << "All strings can be made the same by interchanging characters." << std::endl;
} else {
std::cout << "All strings cannot be made the same by interchanging characters." << std::endl;
}
return 0;
}
輸出
All strings can be made the same by interchanging characters.
import java.util.Arrays;
public class Main {
public static boolean canBeMadeSame(String[] strArray) {
int[][] freqArrays = new int[strArray.length][26]; // 2D array for frequency counts
// Initialize the frequency arrays with zeros
for (int i = 0; i < strArray.length; i++) {
Arrays.fill(freqArrays[i], 0);
}
// Count the frequency of each character in each string
for (int i = 0; i < strArray.length; i++) {
for (char ch : strArray[i].toCharArray()) {
freqArrays[i][ch - 'a']++;
}
}
// Check if frequency arrays of all strings are the same
for (int i = 1; i < freqArrays.length; i++) {
for (int j = 0; j < 26; j++) {
if (freqArrays[i - 1][j] != freqArrays[i][j]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
String[] strArray = {"abb", "bba", "bab"};
if (canBeMadeSame(strArray)) {
System.out.println("All strings can be made the same by interchanging characters.");
} else {
System.out.println("All strings cannot be made the same by interchanging characters.");
}
}
}
輸出
All strings can be made the same by interchanging characters.
def can_be_made_same(str_array):
freq_arrays = [] # List of frequency arrays
# Count the frequency of each character in each string
for s in str_array:
freq_array = [0] * 26 # Initialize the frequency array with zeros
for ch in s:
freq_array[ord(ch) - ord('a')] += 1
freq_arrays.append(freq_array)
# Check if frequency arrays of all strings are the same
for i in range(1, len(freq_arrays)):
if freq_arrays[i - 1] != freq_arrays[i]:
return False
return True
str_array = ["abb", "bba", "bab"]
if can_be_made_same(str_array):
print("All strings can be made the same by interchanging characters.")
else:
print("All strings cannot be made the same by interchanging characters.")
輸出
All strings can be made the same by interchanging characters.
時間複雜度（高效） − O(n * m)，其中n是陣列中字串的數量，m是陣列中字串的最大長度。
結論
在本文中，我們探討了檢查陣列中所有字串是否可以透過交換字元使其相同的問題。我們討論了兩種解決此問題的簡單方法和高效方法，以及它們的演算法和時間複雜度。高效的方法（使用頻率陣列來比較字元出現的次數）比簡單的方法在時間複雜度方面有了顯著的改進。
更新於：2023年10月16日
93 次瀏覽
廣告