Vérifie si une chaîne peut former une chaîne palindrome en échangeant des paires de caractères au niveau des indices avec des caractères inégaux dans une chaîne binaire

Énoncé du problème

Nous avons une chaîne str et une chaîne binaire B. La longueur des deux chaînes est égale à N. Nous devons vérifier si nous pouvons faire de la chaîne str une chaîne palindrome en échangeant ses caractères plusieurs fois sur n'importe quelle paire d'index contenant des caractères inégaux dans la chaîne B.

Exemple Exemple

Entrez

str = ‘AAS’ B = ‘101’

Sortie

‘YES’

La traduction chinoise de

Explication

est :

Explication

Nous pouvons échanger str[1] et str[2] car B[1] et B[2] ne sont pas égaux. La chaîne finale peut être « ASA ».

Entrez

str = ‘AASS’ B = ‘1111’

Sortie

‘No’

La traduction chinoise de

Explication

est :

Explication

Nous ne pouvons pas créer de palindrome de chaîne car la chaîne B ne contient pas de caractères inégaux.

Entrez

str = ‘AASSBV’ B = ‘111100’

Sortie

‘No’

La traduction chinoise de

Explication

est :

Explication

Nous ne pouvons pas faire de la chaîne str un palindrome en raison d'une inadéquation de fréquence de caractères.

Méthode 1

Dans la première méthode, nous vérifierons si une chaîne palindrome peut être créée en utilisant tous les caractères de la chaîne str. Si tel est le cas, nous pouvons vérifier si nous pouvons échanger les caractères dans les paires d'index contenant des caractères inégaux dans la chaîne B et faire de la chaîne un palindrome. Sinon, nous renvoyons false.

Algorithme

• Étape 1 - Exécutez la fonction utility() et échangez des caractères selon la condition donnée pour déterminer si la chaîne peut devenir un palindrome en échangeant des caractères.

• Étape 2 - Définissez la fonction canBePalindromic() pour vérifier si nous pouvons construire une chaîne palindrome en utilisant les caractères de str.

• Étape 2.1 - Créez une carte qui stocke chaque caractère dans la chaîne str et sa fréquence. Utilisez une boucle for pour parcourir la chaîne et compter la fréquence des caractères.

• Étape 2.2 - Comptez le nombre de caractères avec des fréquences paires et impaires.

• Étape 2.3 - Utilisez set pour obtenir le nombre total de caractères uniques dans une chaîne.

• Étape 2.4 - Renvoie vrai si la longueur de la chaîne est impaire et ne contient qu'un seul caractère avec une fréquence impaire.

• Étape 2.5 - Si la longueur de la chaîne est paire, alors tous les caractères de fréquence paire et 0 caractère de fréquence impaire renvoient vrai.

• Étape 2.6 − Renvoie faux.

• Étape 3 - Si la chaîne ne peut pas être un palindrome, renvoyez false.

• Étape 4 - Si la chaîne B contient plusieurs « 1 » et « 0 », renvoyez vrai, sinon renvoyez faux ;

Exemple

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

Sortie

Yes

• Complexité temporelle - O(NlogN), car nous utilisons une boucle for pour parcourir la chaîne, et la méthode insert() de set prend (logN) du temps.

• Complexité spatiale - O(K), où K est le nombre total de caractères uniques.

Méthode 2

Dans cette méthode, au lieu d'utiliser une carte, nous utiliserons un tableau pour stocker la fréquence des caractères.

Algorithme

• Étape 1 - Créez un tableau 'charFrequancy' de longueur 26 et initialisez-le à zéro.

• Étape 2 - Comptez le nombre total de 1 et de 0 dans la chaîne B.

• Étape 3 - Mettez à jour la fréquence de chaque caractère du tableau.

• Étape 4 - Si la longueur de la chaîne est paire et que la fréquence impaire est non nulle, renvoyez false.

• Étape 5 - Si la longueur de la chaîne est impaire et que la fréquence impaire est supérieure à 1, renvoyez false.

• Étape 6 - Renvoie vrai si 1 et 0 existent dans la chaîne.

• Étape 7 - Retournez false.

Exemple

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

Sortie

Yes

• Complexité temporelle - O(N) car nous utilisons une boucle for pour parcourir la chaîne.

• Complexité spatiale − O(1) puisque nous utilisons toujours un tableau de longueur 26.

Conclusion

Nous avons appris deux méthodes pour vérifier si une chaîne peut devenir un palindrome en échangeant des caractères en fonction d'une condition donnée. La première méthode utilise des collections et des cartes, tandis que la seconde méthode utilise uniquement des tableaux pour stocker les données. La deuxième méthode est meilleure que la première méthode car la méthode insert() prend un temps O(logn) pour insérer des données dans la collection, alors que le tableau ne prend qu'un temps O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!