Check if all strings in an array can be made identical by swapping characters

In this article, we will explore the problem of checking if all strings in an array are the same by swapping characters. We will first understand the problem statement and then study simple and efficient ways to solve the problem, along with their respective algorithms and time complexity. Finally, we will implement the solution in C.

Problem Statement

Given an array of strings, determine whether all strings can be made the same by swapping characters.

Naive method

The simplest way is to sort the characters of each string in the array and then compare each sorted string to the next sorted string. If all sorted strings are equal, it means that all strings can be made equal by swapping characters.

Algorithm (simple)

• Sort the characters of each string in the array.

• Compare each sorted string to the next sorted string.

• Returns true if all sorted strings are equal; otherwise, returns false.

C code (plain)

Example

#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;
}

Output

All strings can be made the same by interchanging characters.

Time complexity (naive): O(n * m * log(m)), where n is the number of strings in the array and m is the maximum length of the strings in the array.

Efficient method

What works is to count the frequency of each character in each string and store the count in a frequency array. Then, compare the frequency arrays of all strings. If they are equal, it means that all strings can be made the same by swapping characters.

Algorithm (efficient)

• Initialize the frequency array vector for each string in the array.

• Count the frequency of occurrence of each character in each string and store it in the corresponding frequency array.

• Compare frequency arrays of all strings.

• Returns true if all frequency arrays are equal; otherwise, returns false.

C code (efficient)

Example

#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;
}

Output

All strings can be made the same by interchanging characters.

Time complexity (efficient) - O(n * m), where n is the number of strings in the array and m is the maximum length of the strings in the array.

in conclusion

In this article, we explored the problem of checking if all strings in an array are the same by swapping characters. We discuss simple yet efficient methods for solving this problem, along with their algorithmic and time complexity. This efficient method uses a frequency array to compare the number of occurrences of a character, resulting in a significant improvement in time complexity compared to the simpler method.

The above is the detailed content of Check if all strings in an array can be made identical by swapping characters. For more information, please follow other related articles on the PHP Chinese website!