Macht die angegebenen binären Zeichenfolgen gleich, indem wiederholt zwei aufeinanderfolgende Nullen durch eine einzelne 1 ersetzt werden

In jeder Programmiersprache ist eine Binärzeichenfolge eine Sammlung der Zeichen 0 und 1. In jeder Phase folgt die binäre Zeichenfolge dem Ansatz, dass die Zeichenfolge nur diese beiden Zeichen enthalten kann.

Zeichen in einer fortlaufenden Zeichenfolge sind Zeichen, deren Indizes sich um 1 unterscheiden. Betrachten wir zwei Indizes, i und j, sie heißen stetig, wenn |j-i|.

Wenn in C++ zwei Zeichenfolgen gleichwertig sind, bedeutet dies:

• Die entsprechenden Zeichen in den beiden Zeichenfolgen sind gleich.

• Die Längen der Zeichenfolgen sind gleich und die Zeichen an den entsprechenden Indizes stimmen überein.

Einige Beispiele zur Veranschaulichung der Problemstellung sind wie folgt -

Beispiel Beispiel

str1 - „10001“

str2 - „101“

Lösung-

str1 kann nicht in str2 konvertiert werden, da wir beim Konvertieren von str1 zur Erstellung der entsprechenden Zeichenfolge str2 str1 als „1011“ und str2 als „101“ erhalten.

Beispiel 2 – Betrachten wir die folgende Eingabe −

str1 - „001“

str2 - „11“

Lösung-

str1 kann in str2 umgewandelt werden, indem die ersten beiden Nullen in eine 1 geändert werden.

Verwenden Sie Zeichenabgleich und String-Traversal in C++, um die folgenden Probleme zu lösen.

Algorithmus

• Schritt 1 – Zwei Zeiger i und j werden verwendet, um die Zeichenfolgen s1 und s2 gleichzeitig zu iterieren.

• Schritt 2 – Wenn die Zeichen bei beiden Indizes übereinstimmen, erhöhen wir die i- und j-Zeiger.

• Schritt 3 − Wenn die Zeichen nicht gleich sind, prüfen wir, ob das Zeichen am i-ten und (i+1)-ten Index „0“ ist und ob das Zeichen am j-ten Index „1“ ist '.

• Schritt 4 – Wenn eine solche Situation vorliegt, kann die Konvertierung durchgeführt werden. Der i-Zeiger wird um zwei Positionen und j um eine Indexposition erhöht, da beide Nullen in Einsen umgewandelt werden.

• Schritt 5 – Wenn die Zeichen nicht gleich sind und die obige Situation nicht vorliegt, kann die Konvertierung nicht durchgeführt werden.

• Schritt 6 − Wenn beide Zeiger i und j erfolgreich die Endposition erreichen, kann s1 in s2 umgewandelt werden.

Beispiel

Der folgende Codeausschnitt verwendet zwei Binärzeichenfolgen als Eingabe und prüft, ob die beiden Zeichenfolgen durch einfache Zeichenersetzung basierend auf angegebenen Bedingungen gleichwertig sein können

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

Ausgabe

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

Fazit

Da diese Methode Eingabezeichenfolgen effizient Zeichen für Zeichen vergleichen kann, beträgt die Zeitkomplexität O(min(Zeichenfolgenlänge)). Das Durchlaufen von Strings ist ein wichtiger Aspekt bei der Lösung von Stringproblemen.

Das obige ist der detaillierte Inhalt vonMacht die angegebenen binären Zeichenfolgen gleich, indem wiederholt zwei aufeinanderfolgende Nullen durch eine einzelne 1 ersetzt werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!