Menyemak sama ada rentetan boleh membentuk rentetan palindrom dengan menukar pasangan aksara pada indeks dengan aksara tidak sama dalam rentetan binari

Pernyataan Masalah

Kami mempunyai rentetan str dan rentetan binari B. Panjang kedua-dua rentetan adalah sama dengan N. Kita perlu menyemak sama ada kita boleh membuat rentetan str rentetan palindrom dengan menukar aksaranya beberapa kali pada mana-mana pasangan indeks yang mengandungi aksara tidak sama dalam rentetan B.

Contoh Contoh

Masuk

str = ‘AAS’ B = ‘101’

Output

‘YES’

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kita boleh menukar str[1] dan str[2] kerana B[1] dan B[2] adalah tidak sama. Rentetan akhir boleh menjadi 'ASA'.

Masuk

str = ‘AASS’ B = ‘1111’

Output

‘No’

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kami tidak boleh membuat string palindrom kerana rentetan B tidak mengandungi aksara yang tidak sama rata.

Masuk

str = ‘AASSBV’ B = ‘111100’

Output

‘No’

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kami tidak boleh menjadikan rentetan str sebagai palindrom kerana ketidakpadanan kekerapan aksara.

Kaedah 1

Dalam kaedah pertama kami akan menyemak sama ada sebarang rentetan palindrom boleh dibuat menggunakan semua aksara rentetan str. Jika ya, kita boleh menyemak sama ada kita boleh menukar aksara dalam pasangan indeks yang mengandungi aksara tidak sama dalam rentetan B dan menjadikan rentetan itu sebagai palindrom. Jika tidak, kami kembali palsu.

Algoritma

• Langkah 1 - Laksanakan fungsi utiliti() dan tukar aksara mengikut syarat yang diberikan untuk menentukan sama ada rentetan itu boleh menjadi palindrom dengan menukar aksara.

• Langkah 2 - Tentukan fungsi canBePalindromic() untuk menyemak sama ada kita boleh membina sebarang rentetan palindrom menggunakan aksara str.

• Langkah 2.1 − Buat peta yang menyimpan setiap aksara dalam rentetan str dan kekerapannya. Gunakan gelung for untuk melelaran melalui rentetan dan mengira kekerapan aksara.

• Langkah 2.2 - Kira bilangan aksara dengan frekuensi genap dan ganjil.

• Langkah 2.3 - Gunakan set untuk mendapatkan jumlah bilangan aksara unik dalam rentetan.

• Langkah 2.4 − Kembalikan benar jika panjang rentetan adalah ganjil dan mengandungi hanya satu aksara dengan kekerapan ganjil.

• Langkah 2.5 − Jika panjang rentetan genap, maka semua aksara dengan kekerapan genap dan 0 aksara dengan kekerapan ganjil, kembali benar.

• Langkah 2.6 − Kembalikan palsu.

• Langkah 3 - Jika rentetan itu tidak boleh menjadi palindrom, kembalikan palsu.

• Langkah 4 - Jika rentetan B mengandungi berbilang '1' dan '0', kembalikan benar;

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to check if the string can be palindromic
bool canBePalindromic(string str){
   //Creating the map to store the frequency of each character
   map<char, int> charMap;
   // store the frequency of each character of string Str
   for (int i = 0; i < str.length(); i++) {
      charMap[str[i]] += 1;
   }
   // to store the count of even and odd frequent characters
   int even = 0, odd = 0;
   // iterate through the map
   for (auto e : charMap)  {
      //If frequency is odd, increment odd count; else, increment even count
      if (e.second % 2 == 1) {
         odd++;
      } else {
         even++;
      }
   }
   // set to store unique characters of string Str
   unordered_set<char> set;
   //Insert all characters of string Str in set
   for (int i = 0; i < str.size(); i++){
      set.insert(str[i]);
   }
   // if the string length is odd and only one character has an odd frequency, return true
   if (str.size() % 2 == 1 && even == set.size() - 1 && odd == 1){
      return true;
   }
   // If the string length is even and all characters have even frequency, return true
   if (str.size() % 2 == 0 && even == set.size() && odd == 0){
      return true;
   }
   // else return false
   return false;
}
// function to check if the string can be palindromic by swapping characters according to string B
bool utility(string S, string B){
   // If string S cannot be palindromic, return false.
   if (canBePalindromic(S) == false){
      return false;
   } else{
      // if at least one '1' and '0' is present in string B, string S can be palindromic
      int one = 0, zero = 0;
      for (int i = 0; i < B.size(); i++) {
         // If the current character is '0.'
         if (B[i] == '0'){
            zero++;
         } else {
            one++;
         }
      }
      // return true if at least one '1' and '0' is present in the string B
      if (one >= 1 && zero >= 1){
         return true;
      } else {
         return false;
      }
   }
}
int main(){
   string S = "NANA";
   string B = "0001";
   bool result = utility(S, B);
   if (result)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

Output

Yes

• Kerumitan masa - O(NlogN), kerana kami menggunakan gelung for untuk melintasi rentetan, dan kaedah insert() set mengambil masa (logN).

• Kerumitan Ruang - O(K), dengan K ialah jumlah bilangan aksara unik.

Kaedah 2

Dalam kaedah ini, daripada menggunakan peta, kami akan menggunakan tatasusunan untuk menyimpan kekerapan aksara.

Algoritma

• Langkah 1 - Buat tatasusunan 'charFrequancy' dengan panjang 26 dan mulakannya kepada sifar.

• Langkah 2 - Kira jumlah bilangan 1 dan 0 dalam rentetan B.

• Langkah 3 - Kemas kini kekerapan setiap aksara dalam tatasusunan.

• Langkah 4 - Jika panjang rentetan genap dan frekuensi ganjil bukan sifar, kembalikan palsu.

• Langkah 5 - Jika panjang rentetan ganjil dan frekuensi ganjil lebih besar daripada 1, kembalikan palsu.

• Langkah 6 - Kembalikan benar jika kedua-dua 1 dan 0 wujud dalam rentetan.

• Langkah 7 - Kembalikan palsu.

Contoh

#include <bits/stdc++.h>
using namespace std;
// function to check if the given string can be converted to a palindrome
bool utility(string str, string B){
   // array to store character counts in str
   int charFrequancy[26] = {0};
   int ones = 0, zeros = 0, odd_fre = 0;
   // count ones and zeros
   for (char ch : B) {
      if (ch == '1')
         ones++;
      if (ch == '0')
         zeros++;
   }
   // store counts of characters
   for (char ch : str){
      charFrequancy[ch - 'A']++;
   }
   // check total character with odd frequency
   for (int i = 0; i < 26; i++){
      if (charFrequancy[i] % 2 == 1)
         odd_fre++;
   }
   if (str.length() % 2 == 0 && odd_fre != 0)
      return false;
   if (str.length() % 2 == 1 && odd_fre > 1)
      return false;
   if (ones > 0 && zeros > 0)
      return true;
   return false;
}
int main(){
   string S = "NBCNB";
   string B = "01010";
   if (utility(S, B)){
      cout << "Yes";
   } else {
      cout << "No";
   }
   return 0;
}

Output

Yes

• Kerumitan masa - O(N) kerana kami menggunakan gelung for untuk mengulangi rentetan.

• Kerumitan ruang − O(1) kerana kami sentiasa menggunakan tatasusunan panjang 26.

Kesimpulan

Kami mempelajari dua kaedah untuk menyemak sama ada rentetan boleh menjadi palindrom dengan menukar aksara berdasarkan syarat tertentu. Kaedah pertama menggunakan koleksi dan peta, manakala kaedah kedua hanya menggunakan tatasusunan untuk menyimpan data. Kaedah kedua adalah lebih baik daripada kaedah pertama kerana kaedah insert() mengambil masa O(logn) untuk memasukkan data ke dalam koleksi, manakala tatasusunan hanya mengambil masa O(1).

Atas ialah kandungan terperinci Menyemak sama ada rentetan boleh membentuk rentetan palindrom dengan menukar pasangan aksara pada indeks dengan aksara tidak sama dalam rentetan binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!