在这个问题中，我们需要通过翻转第一个二进制字符串的前缀来将其转换为第二个二进制字符串。为了获得最小的前缀翻转次数，我们需要遍历字符串的末尾，如果在两个字符串中找到不匹配的字符，我们需要翻转第一个字符串的前缀。
问题陈述 − 我们给出了两个不同的二进制字符串，分别称为first和second。两个二进制字符串的长度相等，为N。我们需要通过翻转第一个字符串的前缀将其转换为第二个字符串。在这里，我们需要计算将一个字符串转换为另一个字符串所需的总前缀翻转次数。翻转意味着将‘0’转换为‘1’，将‘1’转换为‘0’。
Sample Examples
Input – first = "001", second = "000"
Output – 2
Explanation
First, we need to flip the prefix of length 3 for the first string, and the resultant string will be 110.
在此之后，我们需要翻转长度为2的前缀，结果字符串将为000，与第二个字符串相等。
Input – first = "10", second = "01"
Output – 1
Explanation
We require to flip the prefix of length 2, and the resultant string will be ‘01’, which is equal to the second string.
Input – first = "11", second = "11"
Output – 0
Explanation
由于两个字符串相等，我们不需要进行任何翻转。
Approach 1
在这种方法中，我们从字符串的最后开始迭代，如果找到不匹配的字符，我们会翻转长度为‘I + 1’的前缀中的所有字符。这是解决问题的一种简单方法。
算法
步骤 1 - 定义变量 'cnt' 并将其初始化为 0。
Step 2 − Start traversing the string from the end using the loop.
Step 3 − If first[i] and second[i] are not equal, we need to flip all the characters of the prefix whose length is equal to the I + 1.
Step 4 − Use the nest for loop to iterate through the prefix of length equal to I + 1, and flip each character of it by executing the flipBits() function.
Step 4.1 − We return ‘0’ if the current character is ‘1’ and ‘1’ if the current character is ‘0’ in the flipBits() function.
Step 5 − Increase the value of the ‘cnt’ variable by 1 when we flip the prefix.
步骤 6 - 返回 'cnt' 变量的值。
Example
#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
// if the bit is '0', flip it to '1', else flip it to '0'.
return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
// to store the count of flips
int cnt = 0;
// Traverse the string
for (int i = n - 1; i >= 0; i--){
// If first[i] is not equal to second[i]
if (first[i] != second[i]){
// flip the bits
for (int j = 0; j <= i; j++){
first[j] = flipBits(first[j]);
}
cnt++;
}
}
return cnt;
}
int main(){
string first = "001", second = "000";
int N = first.size();
cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
return 0;
}
Output
The minimum number of flips of prefixes required to convert the first binary string to the second is - 2
Approach 2
In this approach, we will use the ‘inverted’ variable to track whether the current bit is flipped or not, rather than flipping each prefix bit every time. We also optimized the time complexity of the code in this approach.
算法
Step 1 − Define the ‘cnt’ variable and initialize it with ‘0’. Also, define the ‘inverted’ variable and initialize it with a false value.
步骤 2 - 从末尾开始遍历字符串。如果第一个[i]和第二个[i]字符不匹配，请按照以下步骤操作。
Step 2.1 − If the value of the ‘inverted’ is false, increase the value of the ‘cnt’ variable by 1, and change the value of the ‘inverted’ variable to true.
Step 3 − If both characters match, and the value of the ‘inverted’ is true, we need to flip the bit again. So, increase the value of ‘cnt’ by 1, and change the value of ‘inverted’ to false.
Example
Let’s debug the above algorithm by taking the example.
Input – first = ‘001’, second = ‘000’
在第一步中，第一个[2]和第二个[2]不匹配，'inverted'的值为false。因此，'cnt'的值将变为1，'inverted'将变为true。在这里，通过将'inverted'的值更改为true，我们假设我们已经虚拟地翻转了前缀。
After that, the first[1] and second[1] match, but the value of the ‘inverted’ is true. So, the ‘cnt’ value will become 2, and the ‘inverted’ is false.
Next, the first[0] and second[0] match, and the value of ‘inverted’ is false. So, we don’t need to perform any operation.
最后，它返回值为‘cnt’，其值为2。
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){
// number of flips
int cnt = 0;
// to track whether the current bit is already flipped.
// When we flip a bit 2 times, it becomes the same as the original bit.
bool inverted = false;
// Traverse the given string
for (int i = N - 1; i >= 0; i--){
// If A[i] is not equal to B[i]
if (first[i] != second[i]){
// If the current bit is not already flipped
if (!inverted){
cnt++; // Increase the count of flips
inverted = true; // Invert all prefix bits
}
}
else{
// If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
if (inverted){
// Increase the count of flips
cnt++;
// Update inverted to false
inverted = false;
}
}
}
return cnt;
}
int main(){
string first = "001", second = "000";
int N = first.size();
cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
return 0;
}
Output
The minimum number of flips of prefixes required to convert the first binary string to the second is - 2
Conclusion
我们学习了两种方法来找到将一个字符串转换为另一个字符串所需的最小前缀翻转次数。逻辑是从末尾遍历字符串，如果我们发现不匹配的字符，则翻转前缀。
我们在时间复杂度方面优化了第二段代码，通过使用“inverted”变量来跟踪翻转前缀，而不是像第一种方法那样翻转前缀。
