Prüft, ob eine Zeichenfolge durch Vertauschen von Zeichenpaaren an Indizes mit ungleichen Zeichen in einer Binärzeichenfolge eine Palindromzeichenfolge bilden kann

Problemstellung

Wir haben einen String str und einen binären String B. Die Länge beider Saiten ist gleich N. Wir müssen prüfen, ob wir String str zu einem Palindrom-String machen können, indem wir seine Zeichen mehrmals auf jedem Indexpaar austauschen, das ungleiche Zeichen in String B enthält.

Beispiel Beispiel

Eintreten

str = ‘AAS’ B = ‘101’

Ausgabe

‘YES’

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Wir können str[1] und str[2] vertauschen, weil B[1] und B[2] nicht gleich sind. Die letzte Zeichenfolge kann „ASA“ sein.

Eintreten

str = ‘AASS’ B = ‘1111’

Ausgabe

‘No’

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Wir können die Zeichenfolge nicht palindromisieren, da Zeichenfolge B keine ungleichen Zeichen enthält.

Eintreten

str = ‘AASSBV’ B = ‘111100’

Ausgabe

‘No’

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Wir können die Zeichenfolge str nicht in ein Palindrom umwandeln, da die Zeichenhäufigkeit nicht übereinstimmt.

Methode 1

Bei der ersten Methode prüfen wir, ob eine Palindrom-Zeichenfolge mit allen Zeichen der Zeichenfolge str erstellt werden kann. Wenn ja, können wir prüfen, ob wir die Zeichen in den Indexpaaren mit ungleichen Zeichen in Zeichenfolge B austauschen und die Zeichenfolge in ein Palindrom umwandeln können. Andernfalls geben wir false zurück.

Algorithmus

• Schritt 1 – Führen Sie die Funktion „utility()“ aus und tauschen Sie Zeichen gemäß der angegebenen Bedingung aus, um festzustellen, ob die Zeichenfolge durch den Austausch von Zeichen zu einem Palindrom werden kann.

• Schritt 2 – Definieren Sie die Funktion canBePalindromic(), um zu prüfen, ob wir mit den Zeichen von str eine beliebige Palindromzeichenfolge erstellen können.

• Schritt 2.1 − Erstellen Sie eine Karte, die jedes Zeichen in der Zeichenfolge str und seine Häufigkeit speichert. Verwenden Sie eine for-Schleife, um die Zeichenfolge zu durchlaufen und die Häufigkeit der Zeichen zu zählen.

• Schritt 2.2 – Zählen Sie die Anzahl der Zeichen mit gerader und ungerader Häufigkeit.

• Schritt 2.3 – Verwenden Sie set, um die Gesamtzahl der eindeutigen Zeichen in einer Zeichenfolge zu ermitteln.

• Schritt 2.4 - Geben Sie true zurück, wenn die Zeichenfolgenlänge ungerade ist und nur ein Zeichen mit ungerader Häufigkeit enthält.

• Schritt 2.5 − Wenn die Zeichenfolgenlänge gerade ist, geben alle Zeichen mit gerader Häufigkeit und 0 Zeichen mit ungerader Häufigkeit „true“ zurück.

• Schritt 2.6 − Geben Sie false zurück.

• Schritt 3 – Wenn die Zeichenfolge kein Palindrom sein kann, geben Sie false zurück.

• Schritt 4 – Wenn Zeichenfolge B mehrere „1“ und „0“ enthält, geben Sie true zurück, andernfalls geben Sie false zurück.

Beispiel

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

Ausgabe

Yes

• Zeitkomplexität - O(NlogN), weil wir eine for-Schleife verwenden, um die Zeichenfolge zu durchlaufen, und die insert()-Methode von set (logN) Zeit benötigt.

• Raumkomplexität – O(K), wobei K die Gesamtzahl der eindeutigen Zeichen ist.

Methode 2

Bei dieser Methode verwenden wir anstelle einer Karte ein Array, um die Häufigkeit von Zeichen zu speichern.

Algorithmus

• Schritt 1 – Erstellen Sie ein „charFrequancy“-Array mit der Länge 26 und initialisieren Sie es auf Null.

• Schritt 2 – Zählen Sie die Gesamtzahl der Einsen und Nullen in Zeichenfolge B.

• Schritt 3 – Aktualisieren Sie die Häufigkeit jedes Zeichens im Array.

• Schritt 4 – Wenn die Stringlänge gerade und die ungerade Häufigkeit ungleich Null ist, geben Sie „false“ zurück.

• Schritt 5 – Wenn die Stringlänge ungerade ist und die ungerade Häufigkeit größer als 1 ist, geben Sie „false“ zurück.

• Schritt 6 – Gibt true zurück, wenn sowohl 1 als auch 0 in der Zeichenfolge vorhanden sind.

• Schritt 7 – Geben Sie false zurück.

Beispiel

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

Ausgabe

Yes

• Zeitkomplexität – O(N), weil wir eine for-Schleife verwenden, um über die Zeichenfolge zu iterieren.

• Raumkomplexität − O(1), da wir immer ein Array der Länge 26 verwenden.

Fazit

Wir haben zwei Methoden kennengelernt, um zu überprüfen, ob eine Zeichenfolge zu einem Palindrom werden kann, indem Zeichen basierend auf einer bestimmten Bedingung ausgetauscht werden. Die erste Methode verwendet Sammlungen und Karten, während die zweite Methode nur Arrays zum Speichern von Daten verwendet. Die zweite Methode ist besser als die erste Methode, da die Methode insert() O(logn) Zeit benötigt, um Daten in die Sammlung einzufügen, während das Array nur O(1) Zeit benötigt.

Das obige ist der detaillierte Inhalt vonPrüft, ob eine Zeichenfolge durch Vertauschen von Zeichenpaaren an Indizes mit ungleichen Zeichen in einer Binärzeichenfolge eine Palindromzeichenfolge bilden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!