Dadas dos strings binarias str1 y str2 . La tarea es verificar si es posible convertir str1 a str2 aplicando la siguiente operación un número arbitrario de veces en str1. En cada operación, uno puede combinar dos 0
consecutivos en un solo 1 . Ejemplos:
Entrada: str1 = “00100”, str2 = “111”
Salida: Sí
Combine los dos primeros ceros en uno y combine los dos últimos ceros en uno.
Entrada: str1 = “00”, str2 = “000”
Salida: No
No es posible convertir str1 a str2.
Enfoque: procesemos str1 y str2 carácter por carácter de izquierda a derecha en paralelo. Usemos dos índices i y j: el índice i es para str1 y el índice j es para str2. Ahora bien, hay dos casos:
- Si str1[i] = str2[j] entonces incremente tanto i como j .
- Si str1[i] != str2[j] entonces,
- Si hay dos 0 consecutivos en str1, es decir , str1[i] = 0 y str1[i + 1] = 0 y str2[j] = 1 , lo que significa que ambos ceros se pueden combinar para que coincidan con el 1 en str2 . Por lo tanto, incrementa i en 2 y j en 1 .
- De lo contrario , str1 no se puede convertir a str2 .
- Si al final, tanto i como j están al final de sus respectivas strings, es decir , str1 y str2 , entonces la respuesta es Sí ; de lo contrario, la respuesta es No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if str1 can be
// converted to str2 with the given operations
bool canConvert(string str1, string str2)
{
int i = 0, j = 0;
// Traverse from left to right
while (i < str1.size() && j < str2.size()) {
// If the two characters do not match
if (str1[i] != str2[j]) {
// If possible to combine
if (str1[i] == '0' && str2[j] == '1'
&& i + 1 < str1.size()
&& str1[i + 1] == '0') {
i += 2;
j++;
}
// If not possible to combine
else {
return false;
}
}
// If the two characters match
else {
i++;
j++;
}
}
// If possible to convert one string to another
if (i == str1.size() && j == str2.size())
return true;
return false;
}
// Driver code
int main()
{
string str1 = "00100", str2 = "111";
if (canConvert(str1, str2))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true if str1 can be
// converted to str2 with the given operations
static boolean canConvert(String str1, String str2)
{
int i = 0, j = 0;
// Traverse from left to right
while (i < str1.length() && j < str2.length())
{
// If the two characters do not match
if (str1.charAt(i) != str2.charAt(j))
{
// If possible to combine
if (str1.charAt(i) == '0' && str2.charAt(j) == '1'
&& i + 1 < str1.length() && str1.charAt(i+1) == '0')
{
i += 2;
j++;
}
// If not possible to combine
else
{
return false;
}
}
// If the two characters match
else
{
i++;
j++;
}
}
// If possible to convert one string to another
if (i == str1.length() && j == str2.length())
return true;
return false;
}
// Driver code
public static void main(String[] args)
{
String str1 = "00100", str2 = "111";
if (canConvert(str1, str2))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code contributed by Rajput-Ji
Python3
# Python implementation of the approach
# Function that returns true if str1 can be
# converted to str2 with the given operations
def canConvert(str1, str2):
i, j = 0, 0;
# Traverse from left to right
while (i < len(str1) and j < len(str2)):
# If the two characters do not match
if (str1[i] != str2[j]):
# If possible to combine
if (str1[i] == '0' and str2[j] == '1'
and i + 1 < len(str1)
and str1[i + 1] == '0'):
i += 2;
j+=1;
# If not possible to combine
else:
return False;
# If the two characters match
else:
i += 1;
j += 1;
# If possible to convert one string to another
if (i == len(str1) and j == len(str2)):
return True;
return False;
# Driver code
str1 = "00100";
str2 = "111";
if (canConvert(str1, str2)):
print("Yes");
else:
print("No");
# This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if str1 can be
// converted to str2 with the given operations
static bool canConvert(string str1, string str2)
{
int i = 0, j = 0;
// Traverse from left to right
while (i < str1.Length && j < str2.Length)
{
// If the two characters do not match
if (str1[i] != str2[j])
{
// If possible to combine
if (str1[i] == '0' && str2[j] == '1'
&& i + 1 < str1.Length && str1[i+1] == '0')
{
i += 2;
j++;
}
// If not possible to combine
else
{
return false;
}
}
// If the two characters match
else
{
i++;
j++;
}
}
// If possible to convert one string to another
if (i == str1.Length && j == str2.Length)
return true;
return false;
}
// Driver code
public static void Main()
{
string str1 = "00100", str2 = "111";
if (canConvert(str1, str2))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if str1 can be
// converted to str2 with the given operations
function canConvert(str1, str2) {
var i = 0,
j = 0;
// Traverse from left to right
while (i < str1.length && j < str2.length) {
// If the two characters do not match
if (str1[i] !== str2[j]) {
// If possible to combine
if (
str1[i] === "0" &&
str2[j] === "1" &&
i + 1 < str1.length &&
str1[i + 1] === "0"
) {
i += 2;
j++;
}
// If not possible to combine
else {
return false;
}
}
// If the two characters match
else {
i++;
j++;
}
}
// If possible to convert one string to another
if (i === str1.length && j === str2.length) return true;
return false;
}
// Driver code
var str1 = "00100",
str2 = "111";
if (canConvert(str1, str2)) document.write("Yes");
else document.write("No");
</script>
Producción:
Yes
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA