Semak sama ada semua rentetan dalam tatasusunan boleh dibuat sama dengan menukar aksara

Dalam artikel ini, kami akan meneroka masalah menyemak sama ada semua rentetan dalam tatasusunan adalah sama dengan menukar aksara. Kami mula-mula akan memahami penyataan masalah dan kemudian mengkaji cara mudah dan cekap untuk menyelesaikan masalah, bersama-sama dengan algoritma dan kerumitan masa masing-masing. Akhirnya, kami akan melaksanakan penyelesaian dalam C++.

Pernyataan Masalah

Memandangkan tatasusunan rentetan, tentukan sama ada semua rentetan boleh dibuat sama dengan menukar aksara.

Kaedah naif

Cara paling mudah ialah mengisih aksara setiap rentetan dalam tatasusunan dan kemudian membandingkan setiap rentetan diisih dengan rentetan diisih seterusnya. Jika semua rentetan yang diisih adalah sama, ini bermakna semua rentetan boleh dibuat sama dengan menukar aksara.

Algoritma (naif)

• Isih aksara setiap rentetan dalam tatasusunan.

• Bandingkan setiap rentetan diisih dengan rentetan diisih seterusnya.

• Mengembalikan benar jika semua rentetan yang diisih adalah sama;

Kod C++ (biasa)

Contoh

#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.

Kerumitan masa (naif): O(n * m * log(m)), dengan n ialah bilangan rentetan dalam tatasusunan dan m ialah panjang maksimum rentetan dalam tatasusunan.

Kaedah yang cekap

Apa yang berfungsi ialah mengira kekerapan setiap aksara dalam setiap rentetan dan menyimpan kiraan dalam tatasusunan frekuensi. Kemudian, bandingkan tatasusunan kekerapan semua rentetan. Jika mereka sama, ini bermakna semua rentetan boleh dibuat sama dengan menukar aksara.

Algoritma (cekap)

• Mulakan vektor tatasusunan frekuensi untuk setiap rentetan dalam tatasusunan.

• Kira kekerapan kejadian setiap aksara dalam setiap rentetan dan simpannya dalam tatasusunan frekuensi yang sepadan.

• Bandingkan tatasusunan kekerapan semua rentetan.

• Mengembalikan benar jika semua tatasusunan frekuensi adalah sama; jika tidak, mengembalikan palsu.

Kod C++ (cekap)

Contoh

#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.

Kerumitan masa (cekap) - O(n * m), dengan n ialah bilangan rentetan dalam tatasusunan dan m ialah panjang maksimum rentetan dalam tatasusunan.

Kesimpulan

Dalam artikel ini, kami meneroka masalah menyemak sama ada semua rentetan dalam tatasusunan adalah sama dengan menukar aksara. Kami membincangkan kaedah yang mudah tetapi cekap untuk menyelesaikan masalah ini, bersama-sama dengan kerumitan algoritma dan masa mereka. Kaedah cekap ini menggunakan tatasusunan frekuensi untuk membandingkan bilangan kejadian aksara, menghasilkan peningkatan yang ketara dalam kerumitan masa berbanding kaedah yang lebih mudah.

Atas ialah kandungan terperinci Semak sama ada semua rentetan dalam tatasusunan boleh dibuat sama dengan menukar aksara. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!