数据结构
网络
关系数据库管理系统 (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 次浏览
广告