将二进制字符串通过翻转前缀转换为另一个字符串，并使翻转次数最少

前缀是从第零个索引开始的子字符串，其长度可以是 1 到给定字符串长度的任何值。我们得到了两个二进制字符串，这意味着这两个字符串仅包含两种不同的字符，我们需要通过翻转前缀将第一个字符串转换为第二个字符串，并使翻转次数最少。此外，还给定这两个字符串的长度相等。

输入 1

string str1 = "01100"
string str2 = "10101"

输出

3

解释

我们唯一可以执行的操作是选择任意长度的前缀，然后更新其值。因此，我们可以选择整个字符串，则字符串将变为 10011。现在，我们可以选择长度为字符串总长度减 1 的前缀，则字符串将变为 01101。最后，我们可以选择长度为 2 的前缀，这将给我们答案。

输入 2

 string str1 = “1001” 
 string str2 = “1000”

输出

2

思路

我们可以在这里观察到，如果我们需要通过翻转所选前缀的所有字符来更改字符串。

需要注意的是，如果我们想更改第一个字符串的最后一位，则必须选择整个字符串，然后以后就不需要再选择整个字符串了。

因此，根据这个观察结果，我们可以从最后一位遍历字符串，并检查两个字符串的当前字符是否相同。如果它们相同，则我们移动到下一个字符，否则我们将更新答案并翻转字符串。

现在，翻转整个字符串是一个代价较高的步骤，因此与其翻转整个字符串，不如使用一个变量来标记字符串是否被翻转。

如果字符串翻转一次，则字符将发生变化，但如果我们翻转字符串两次，则字符串将恢复到相同的形式。

代码实现步骤

  • 首先，我们将创建一个主函数，并定义字符串，并调用函数以获取所需的最小步骤数。

  • 我们的辅助函数将把两个字符串作为参数，并返回一个整数，该整数将是我们所需的数字。

  • 在函数中，我们将获取字符串的长度并将其存储在一个变量中。

  • 将有一个布尔变量来存储当前字符串是否被翻转。

  • 我们将使用 for 循环从最后一个索引到第零个索引遍历字符串。

  • 如果两个字符串的当前字符相同且字符串被翻转，或者字符不同且字符串未被翻转，则我们将答案更新为 1 并翻转字符串。

  • 最后，我们将返回答案值，并在主函数中打印它。

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;
// creating a function to find number of steps required 
int stepsReq(string str1, string str2){
   int len = str1.length(); // getting length of the strings
   int ans = 0; // variable to store the answer 
   bool isFlipped = false;
   // traversing over the string 
   for(int i=len-1; i>=0; i--){
      if(str1[i] == str2[i]){
         if(isFlipped){
            // characters are the same but the string is flipped ans++;
            isFlipped = false;
         }
       } else{
          if(!isFlipped){
             // characters are not the same and the string is not flipped 
             isFlipped = true;
             ans++;
          }
       }
   }
   return ans; // return the answer 
}
int main(){
   string str1 = "01100"; // given strings 
   string str2 = "10101";
   // calling the function 
   cout<<"The minimum number of steps required to convert the first string to another by flipping the prefixes is" <<stepsReq(str1,str2)<<endl;
   return 0; 
}

输出

The minimum number of steps required to convert the first string to another by flipping the prefixes is 2

时间和空间复杂度

上述代码的时间复杂度为 O(N)，其中 N 是字符串的长度。

由于我们不使用任何额外的空间，因此上述代码的空间复杂度为 O(1)。

注意

在这个问题中，我们得到两个字符串的长度相同，因此我们没有为它编写任何条件，但如果没有给出，则我们必须为此添加一个条件，并检查如果长度不同，则返回是不可能的。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

在本教程中，我们实现了一个程序，通过翻转前缀将二进制字符串转换为另一个字符串，并使翻转次数最少。前缀是从第零个索引开始的子字符串，其长度可以是 1 到给定字符串长度的任何值。我们实现了一个程序，其时间复杂度为 O(N)，空间复杂度为 O(1)。

更新于： 2023年7月11日

183 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告