Dadas las strings s1 y s2 que consisten en ‘A’, ‘B’ y ‘#’ , donde:
- ‘#’ representa una celda vacía
- ‘A’ representa robots que pueden moverse en la dirección izquierda y
- ‘B’ representa robots que pueden moverse en la dirección correcta
La tarea es verificar si s1 se puede convertir en s2 mediante el movimiento de los robots.
Ejemplos:
Entrada: s1 = “#B#A#”, s2 = “##BA#”
Salida: Sí
Explicación : En un paso, ‘B’ se mueve una posición a la derecha.
Entonces la string se convierte en «##BA#», que es lo mismo que la string final s2Entrada: s1 = “#B#A#”, s2 = “#A#B#”
Salida: No
Explicación: Como los robots no pueden cruzarse entre sí.
Planteamiento: La idea para resolver el problema se basa en la siguiente observación:
Los robots pueden llegar a la posición final cuando las cuerdas cumplen la condición:
- Si los espacios vacíos ‘#’ se eliminan de la string, ambas strings deben ser idénticas, ya que no se permite el cruce de A y B.
- Después de eliminar el ‘#’ de ambas strings, si las posiciones de A son menores en s2 que en s1 y las posiciones de ‘B’ son mayores en s2 que en s1.
Siga los pasos mencionados a continuación para implementar la observación anterior:
- Iterar la array desde el principio:
- Elimine los espacios vacíos ( ‘#’ ) de ambas strings.
- Almacene la posición de A y B en ambas strings
- Si las strings modificadas s1 y s2 son exactamente iguales, pueden alcanzar el estado final cuando:
- La posición de ‘A’ en s1 es mayor o igual que la posición de ‘A’ en s2 y la posición de ‘B’ en s1 es menor o igual que la posición de ‘B’ en s2 .
- En todos los demás casos, los robots no pueden alcanzar las posiciones finales mencionadas en s2 .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to check if robots can move
string moveRobots(string s1, string s2)
{
// Strings to save s1 and s2 without '#'
string a, b;
for (int i = 0; i < s1.size(); i++)
if (s1[i] != '#')
a += s1[i];
for (int i = 0; i < s2.size(); i++)
if (s2[i] != '#')
b += s2[i];
// Condition 1: strings s1 and s2
// without empty spaces should be
// exactly same
if (a == b) {
int n = a.size();
// v1 and v2 will store the
// positions of 'A' or 'B'
// in s1 and s2 respectively
vector<int> v1;
vector<int> v2;
for (int i = 0; i < s1.size(); i++) {
if (s1[i] != '#')
v1.push_back(i);
}
for (int i = 0; i < s2.size(); i++)
if (s2[i] != '#')
v2.push_back(i);
// Condition 2:
// Position of 'A' in s1 should be
// greater than or equal to
// Position of 'A' in s2 and
// Position of 'B' in s1 should be
// less than or equal to
// Position of 'B' in s2
if (a[0] == 'A' and v1[0] < v2[0])
return "No";
if (a[0] == 'B' and v1[0] > v2[0])
return "No";
for (int i = 1; i < n; i++) {
if (a[i] == 'A') {
if (v1[i] < v2[i])
return "No";
}
else {
if (v1[i] > v2[i])
return "No";
}
}
return "Yes";
}
return "No";
}
// Driver code
int main()
{
string s1 = "#B#A#";
string s2 = "##BA#";
cout << moveRobots(s1, s2) << endl;
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG {
// Function to check if robots can move
static String moveRobots(String s1, String s2)
{
// Strings to save s1 and s2 without '#'
String a = "", b = "";
for (int i = 0; i < s1.length(); i++)
if (s1.charAt(i) != '#')
a += s1.charAt(i);
for (int i = 0; i < s2.length(); i++)
if (s2.charAt(i) != '#')
b += s2.charAt(i);
// Condition 1: strings s1 and s2
// without empty spaces should be
// exactly same
if (a.equals(b)) {
int n = a.length();
// v1 and v2 will store the
// positions of 'A' or 'B'
// in s1 and s2 respectively
ArrayList<Integer> v1
= new ArrayList<Integer>();
ArrayList<Integer> v2
= new ArrayList<Integer>();
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != '#')
v1.add(i);
}
for (int i = 0; i < s2.length(); i++)
if (s2.charAt(i) != '#')
v2.add(i);
// Condition 2:
// Position of 'A' in s1 should be
// greater than or equal to
// Position of 'A' in s2 and
// Position of 'B' in s1 should be
// less than or equal to
// Position of 'B' in s2
if (a.charAt(0) == 'A'
&& (int)v1.get(0) < (int)v2.get(0))
return "No";
if (a.charAt(0) == 'B'
&& (int)v1.get(0) > (int)v2.get(0))
return "No";
for (int i = 1; i < n; i++) {
if (a.charAt(i) == 'A') {
if ((int)v1.get(i) < (int)v2.get(i))
return "No";
}
else {
if ((int)v1.get(i) > (int)v2.get(i))
return "No";
}
}
return "Yes";
}
return "No";
}
// Driver code
public static void main(String[] args)
{
String s1 = "#B#A#";
String s2 = "##BA#";
System.out.println(moveRobots(s1, s2));
}
}
// This code is contributed by ukasp.
Python3
# python3 code for the above approach: # Function to check if robots can move def moveRobots(s1, s2): # Strings to save s1 and s2 without '#' a, b = "", "" for i in range(0, len(s1)): if (s1[i] != '#'): a += s1[i] for i in range(0, len(s2)): if (s2[i] != '#'): b += s2[i] # Condition 1: strings s1 and s2 # without empty spaces should be # exactly same if (a == b): n = len(a) # v1 and v2 will store the # positions of 'A' or 'B' # in s1 and s2 respectively v1 = [] v2 = [] for i in range(0, len(s1)): if (s1[i] != '#'): v1.append(i) for i in range(0, len(s2)): if (s2[i] != '#'): v2.append(i) # Condition 2: # Position of 'A' in s1 should be # greater than or equal to # Position of 'A' in s2 and # Position of 'B' in s1 should be # less than or equal to # Position of 'B' in s2 if (a[0] == 'A' and v1[0] < v2[0]): return "No" if (a[0] == 'B' and v1[0] > v2[0]): return "No" for i in range(1, n): if (a[i] == 'A'): if (v1[i] < v2[i]): return "No" else: if (v1[i] > v2[i]): return "No" return "Yes" return "No" # Driver code if __name__ == "__main__": s1 = "#B#A#" s2 = "##BA#" print(moveRobots(s1, s2)) # This code is contributed by rakeshsahni
C#
// C# code for the above approach:
using System;
using System.Collections;
class GFG
{
// Function to check if robots can move
static string moveRobots(string s1, string s2)
{
// Strings to save s1 and s2 without '#'
string a = "", b = "";
for (int i = 0; i < s1.Length; i++)
if (s1[i] != '#')
a += s1[i];
for (int i = 0; i < s2.Length; i++)
if (s2[i] != '#')
b += s2[i];
// Condition 1: strings s1 and s2
// without empty spaces should be
// exactly same
if (a == b) {
int n = a.Length;
// v1 and v2 will store the
// positions of 'A' or 'B'
// in s1 and s2 respectively
ArrayList v1 = new ArrayList();
ArrayList v2 = new ArrayList();
for (int i = 0; i < s1.Length; i++) {
if (s1[i] != '#')
v1.Add(i);
}
for (int i = 0; i < s2.Length; i++)
if (s2[i] != '#')
v2.Add(i);
// Condition 2:
// Position of 'A' in s1 should be
// greater than or equal to
// Position of 'A' in s2 and
// Position of 'B' in s1 should be
// less than or equal to
// Position of 'B' in s2
if (a[0] == 'A' && (int)v1[0] < (int)v2[0])
return "No";
if (a[0] == 'B' && (int)v1[0] > (int)v2[0])
return "No";
for (int i = 1; i < n; i++) {
if (a[i] == 'A') {
if ((int)v1[i] < (int)v2[i])
return "No";
}
else {
if ((int)v1[i] > (int)v2[i])
return "No";
}
}
return "Yes";
}
return "No";
}
// Driver code
public static void Main()
{
string s1 = "#B#A#";
string s2 = "##BA#";
Console.Write(moveRobots(s1, s2));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach:
// Function to check if robots can move
const moveRobots = (s1, s2) => {
// Strings to save s1 and s2 without '#'
let a, b;
for (let i = 0; i < s1.length; i++)
if (s1[i] != '#')
a += s1[i];
for (let i = 0; i < s2.length; i++)
if (s2[i] != '#')
b += s2[i];
// Condition 1: strings s1 and s2
// without empty spaces should be
// exactly same
if (a == b) {
let n = a.length;
// v1 and v2 will store the
// positions of 'A' or 'B'
// in s1 and s2 respectively
let v1 = [];
let v2 = [];
for (let i = 0; i < s1.length; i++) {
if (s1[i] != '#')
v1.push(i);
}
for (let i = 0; i < s2.length; i++)
if (s2[i] != '#')
v2.push(i);
// Condition 2:
// Position of 'A' in s1 should be
// greater than or equal to
// Position of 'A' in s2 and
// Position of 'B' in s1 should be
// less than or equal to
// Position of 'B' in s2
if (a[0] == 'A' && v1[0] < v2[0])
return "No";
if (a[0] == 'B' && v1[0] > v2[0])
return "No";
for (let i = 1; i < n; i++) {
if (a[i] == 'A') {
if (v1[i] < v2[i])
return "No";
}
else {
if (v1[i] > v2[i])
return "No";
}
}
return "Yes";
}
return "No";
}
// Driver code
let s1 = "#B#A#";
let s2 = "##BA#";
document.write(moveRobots(s1, s2));
// This code is contributed by rakeshsahni
</script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 2: – Solución optimizada
Planteamiento: La idea para resolver el problema se basa en la siguiente observación:
Paso 1: – Tome un puntero (digamos i) en la primera string y otro puntero (digamos j) para la segunda string.
Paso 2: – Incremente el puntero de ambas strings hasta que encuentre cualquiera de los BOTS.
Paso 2, CASO 1: – Si los BOTS apuntados por los punteros respectivos no son los mismos, entonces en ese caso la respuesta es NO.
Motivo: – Consideremos dos strings, a saber, S1 = ##A##B# y S2 = ##B##A#
Para lograr el estado representado por S2, es seguro que durante esta transición los BOTS se cruzaron entre sí y solo él puede lograr el estado. Pero de acuerdo con la pregunta, los BOTS no deben cruzarse entre sí y, por lo tanto, la respuesta será NO.
Por lo tanto, si S1[i] == ‘A’ y S2[j] == ‘B’ , entonces en este caso devuelve NO.
Paso 2, CASO 2: – Si los dos BOTS apuntados por los dos punteros son iguales y digamos que A es el bot que se encuentra, entonces debería estar en el siguiente caso: –
Motivo: – Consideremos dos strings, a saber, S1 = ##A##B# y S2 = ###A#B#
Podemos ver que para lograr el estado representado por el S2, A tiene que moverse a la derecha PERO De acuerdo con la pregunta, A solo puede moverse a la izquierda, por lo que no podemos lograr este estado.
Por lo tanto, si S1[i] == ‘A’ y S2[j] == ‘A’ e i<j , entonces en este caso devuelve NO.
Paso 2, CASO 3: – Si los dos BOTS apuntados por los dos punteros son iguales y digamos que B es el bot que se encuentra, entonces debería estar en el siguiente caso: –
Motivo: Consideremos dos strings, a saber, S1 = ##A##B# y S2 = ##AB###
Podemos ver que para alcanzar el estado representado por S2 B tiene que moverse a la izquierda PERO De acuerdo con la pregunta B solo puede moverse a la derecha, por lo que no podemos alcanzar este estado.
Por lo tanto, si S1[i] == ‘B’ y S2[j] == ‘B’ e i>j , entonces en este caso devuelve NO.
Para los demás casos es posible alcanzar el estado representado por S2.
A continuación se muestra la implementación del enfoque anterior: –
C++
// cpp program to check if we can transit from state
// represented by S1 to state represented by State S2
#include <bits/stdc++.h>
using namespace std;
void moveRobots(string s1, string s2)
{
int i = 0, j = 0, n = s1.size();
while (i < n && j < n) {
if (s1[i] == '#')
i++;
else if (s2[j] == '#')
j++;
// Step 2 CASE 1
else if (s1[i] != s2[j])
cout << "No";
// Step 2 CASE 2
else if (s1[i] == 'A' && i < j)
cout << "No";
// Step 2 CASE 3
else if (s1[i] == 'B' && i > j)
cout << "No";
else {
i++;
j++;
}
}
cout << "Yes";
}
int main()
{
string s1 = "#B#A#", s2 = "##BA#";
moveRobots(s1, s2);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// c program to check if we can transit from state
// represented by S1 to state represented by State S2
#include <stdio.h>
#include <string.h>
void moveRobots(char s1[], char s2[])
{
int i = 0, j = 0, n = strlen(s1);
while (i < n && j < n) {
if (s1[i] == '#')
i++;
else if (s2[j] == '#')
j++;
// Step 2 CASE 1
else if (s1[i] != s2[j])
printf("No");
// Step 2 CASE 2
else if (s1[i] == 'A' && i < j)
printf("No");
// Step 2 CASE 3
else if (s1[i] == 'B' && i > j)
printf("No");
else {
i++;
j++;
}
}
printf("Yes");
}
int main()
{
char s1[] = "#B#A#";
char s2[] = "##BA#";
moveRobots(s1, s2);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// java program to check if we can transit from state
// represented by S1 to state represented by State S2
import java.io.*;
import java.util.*;
class BOTS {
public static void moveRobots(String s1, String s2)
{
int i = 0, j = 0;
int n = s1.length();
while (i < n && j < n) {
if (s1.charAt(i) == '#')
i++;
else if (s2.charAt(j) == '#')
j++;
// Step 2 CASE 1
else if (s1.charAt(i) != s2.charAt(j))
System.out.println("No");
// Step 2 CASE 2
else if (s1.charAt(i) == 'A' && i < j)
System.out.println("No");
// Step 2 CASE 3
else if (s1.charAt(i) == 'B' && i > j)
System.out.println("No");
else {
i++;
j++;
}
}
System.out.println("Yes");
}
}
class GFG {
public static void main(String args[])
{
String s1 = "#B#A#";
String s2 = "##BA#";
BOTS obj = new BOTS();
obj.moveRobots(s1, s2);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python
# Python program to check if we can transit from state
# represented by S1 to state represented by State S2
def moveRobots(s1, s2) :
i = 0
j = 0
n = len(s1)
while i < n and j < n :
if s1[i] == '#' :
i+=1
elif s2[j] == '#' :
j+=1
# Step 2 CASE 1
elif s1[i] != s2[j] :
print("No")
# Step 2 CASE 2
elif s1[i] == 'A' and i < j :
print("No")
# Step 2 CASE 3
elif s1[i] == 'B' and i > j :
print("No")
else :
i+=1
j+=1
print("Yes")
# Driver Code
if __name__ == '__main__':
s1 = "#B#A#"
s2 = "##BA#"
moveRobots(s1, s2)
# This code has been contributed by Sachin Sahara (sachin801)
Javascript
<script>
// Javascript program to check if we can transit from state
// represented by S1 to state represented by State S2
const moveRobots = (s1, s2) => {
let i=0, j=0, n=s1.length;
while(i<n && j<n){
if(s1[i]=='#')
i++;
else if(s2[j]=='#')
j++;
// Step 2 CASE 1
else if (s1[i] != s2[j])
document.write("No");
// Step 2 CASE 2
else if (s1[i] == 'A' && i < j)
document.write("No");
// Step 2 CASE 3
else if (s1[i] == 'B' && i > j)
document.write("No");
else{
i++;
j++;
}
}
document.write("Yes");
}
// Driver code
let s1 = "#B#A#";
let s2 = "##BA#";
moveRobots(s1, s2);
// This code is contributed by adityapatil12
</script>
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Driver code
public static void Main(string[] args){
String s1 = "#B#A#";
String s2 = "##BA#";
BOTS obj = new BOTS();
obj.moveRobots(s1, s2);
}
}
public class BOTS {
public void moveRobots(String s1, String s2)
{
int i = 0, j = 0;
int n = s1.Length;
while (i < n && j < n) {
if (s1[i] == '#')
i++;
else if (s2[j] == '#')
j++;
// Step 2 CASE 1
else if (s1[i] != s2[j])
Console.WriteLine("No");
// Step 2 CASE 2
else if (s1[i] == 'A' && i < j)
Console.WriteLine("No");
// Step 2 CASE 3
else if (s1[i] == 'B' && i > j)
Console.WriteLine("No");
else {
i++;
j++;
}
}
Console.WriteLine("Yes");
}
}
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA