在这个问题中，我们需要通过翻转第一个二进制字符串的前缀来将其转换为第二个二进制字符串。为了获得最小的前缀翻转次数，我们需要遍历字符串的末尾，如果在两个字符串中找到不匹配的字符，我们需要翻转第一个字符串的前缀。
问题陈述 − 我们给出了两个不同的二进制字符串，分别称为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
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
