Rend les chaînes binaires données égales en remplaçant à plusieurs reprises deux 0 consécutifs par un seul 1

Dans n'importe quel langage de programmation, une chaîne binaire est une collection de caractères 0 et 1. À chaque étape, la chaîne binaire suit l'approche selon laquelle la chaîne ne peut contenir que ces deux caractères.

Les caractères d'une chaîne continue sont des caractères dont les index diffèrent de 1. Considérons deux indices, i et j, ils sont dits continus si |j-i| = 1.

En C++, si deux chaînes sont équivalentes, cela signifie :

• Les caractères correspondants dans les deux chaînes sont les mêmes.

• Les chaînes sont de longueur égale et les caractères aux indices correspondants coïncident.

Quelques exemples pour illustrer l'énoncé du problème sont les suivants -

Exemple Exemple

str1 - "10001"

str2 - "101"

Solution-

str1 ne peut pas être converti en str2 car lors du processus de conversion de str1 pour créer la chaîne équivalente str2, nous obtiendrons str1 comme "1011" et str2 comme "101".

Exemple 2 - Considérons l'entrée suivante −

str1 - "001"

str2 - "11"

Solution-

str1 peut être converti en str2 en changeant les deux premiers zéros en 1.

Utilisez la correspondance de caractères et le parcours de chaînes en C++ pour résoudre les problèmes suivants.

Algorithme

• Étape 1 - Deux pointeurs i et j sont utilisés pour parcourir les chaînes s1 et s2 simultanément.

• Étape 2 - Si les caractères des deux indices correspondent, nous incrémentons les pointeurs i et j.

• Étape 3 - Si les caractères ne sont pas égaux, nous vérifions si le caractère au i-ème et (i+1)ème index est '0', et si le caractère au j-ème index est '1 '.

• Étape 4 - Si une telle situation existe, la conversion peut être effectuée. Le pointeur i est incrémenté de deux positions et j est incrémenté d'une position d'index car les deux zéros sont convertis en uns.

• Étape 5 - Si les caractères ne sont pas égaux et que la situation ci-dessus n'existe pas, la conversion ne peut pas être effectuée.

• Étape 6 - Si les deux pointeurs i et j atteignent avec succès la position finale, s1 peut être converti en s2.

Exemple

L'extrait de code suivant prend deux chaînes binaires en entrée et vérifie si les deux chaînes peuvent être équivalentes par simple substitution de caractères en fonction de conditions spécifiées

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//convert consecutive 0's to 1
bool convertBinary(string s1, string s2){

   //fetching the lengths of both the strings
   int len1 = s1.length();
   int len2 = s2.length();
   string temp ="";

   //maintaining counters of both the strings
   int i = 0, j = 0;

   //iterating over both the strings simultaneously
   while (i < len1 && j < len2) {

      //if both the characters are equivalent in nature
      //skip to next character
      if (s1[i] == s2[j]) {
         temp+=s1[i];

         //incrementing both pointers
         i++;
         j++;
      }

      // if both characters differ
      else {

         // checking if '00' of s1 can be converted to '1' of s2
         if(s2[j]=='1' && s1[i]=='0'){

            //checking if i+1th index exists and is equivalent to 0
            if(i+1 < len1 && s1[i+1]=='0'){

               //conversion is possible
               //skip two 0's of s1 since converted to 1 in s2
               temp+='1';
               i += 2;
               j++;
            } else {
               return false;
            }
         }

         // If not possible to combine
         else {
            return false;
         }
      }
   }
   cout<<"Entered string2 "<<s2<<"\n";
   cout<<"Converted string1 "<<temp<<"\n";

   //check if both the strings are returned to end position
   if (i == len1 && j == len2)
      return true;
      return false;
}

// calling the conversion rate
int main(){
   string str1 = "100100";
   string str2 = "1111";

   //capturing result
   cout<<"Entered string1 "<<str1<<"\n";
   bool res = convertBinary(str1, str2);
   if (res)
      cout << "First string can be converted to second";
   else
      cout << "First string can't be converted to second";
   return 0;
}

Sortie

Entered string1 100100
Entered string2 1111
Converted string1 1111
First string can be converted to second

Conclusion

Étant donné que cette méthode peut comparer efficacement les chaînes d'entrée caractère par caractère, la complexité temporelle est O(min(string length)). Le parcours de chaînes est un aspect important de la résolution des problèmes de chaînes.

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!