通过重复将两个连续的0替换为单个1，使给定的二进制字符串相等

在任何编程语言中，二进制字符串是由字符0和1组成的集合。在每个阶段，二进制字符串遵循的方法是字符串只能包含这两个字符。

连续字符串中的字符是指索引之间的差为1的字符。让我们考虑两个索引，i和j，如果|j-i| = 1，则它们被称为连续的。

在C++中，如果两个字符串等价，则表示：

• 两个字符串中对应的字符相同。

• 字符串的长度相等，并且相应索引处的字符重合。

说明问题陈述的一些示例如下 -

示例示例

str1 - “10001”

str2 - “101”

解决方案-

str1 无法转换为 str2，因为在将 str1 转换为创建等效字符串 str2 的过程中，我们将得到 str1 为“1011”，而 str2 是“101”。

示例2 - 让我们考虑以下输入−

str1 - “001”

str2 - “11”

解决方案-

str1可以通过将前两个零更改为一个1来转换为str2。

使用C++中的字符匹配和字符串遍历可以解决以下问题。

算法

• 步骤 1 - 两个指针 i 和 j 分别用于同时迭代字符串 s1 和 s2。

• 第 2 步 - 如果两个索引处的字符匹配，我们将增加 i 和 j 指针。

• 步骤 3 − 如果字符不相等，我们检查第i个和第(i+1)个索引处的字符是否为‘0’，以及第j个索引处的字符是否为‘1’。

• 第四步 - 如果存在这样的情况，可以进行转换。i指针增加两个位置，j增加一个索引位置，因为两个零都被转换为一。

• 第五步 - 如果字符不相等，并且上述情况也不存在，则无法进行转换。

• 步骤 6 − 如果指针 i 和 j 都成功到达末尾位置，则可以将 s1 转换为 s2。

示例

以下代码片段将两个二进制字符串作为输入，并根据指定条件检查这两个字符串是否可以通过简单的字符替换来等效

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

输出

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

结论

由于该方法可以有效地逐个字符地比较输入字符串，时间复杂度为 O(min(字符串长度))。字符串遍历是解决字符串问题的一个重要方面。

以上是通过重复将两个连续的0替换为单个1，使给定的二进制字符串相等的详细内容。更多信息请关注PHP中文网其他相关文章！