Dos strings dadas contienen tres caracteres, es decir, ‘A’, ‘B’ y ‘#’ solamente. Verifique si es posible convertir la primera string en otra string realizando las siguientes operaciones en la string primero.
1- ‘A’ solo puede moverse hacia la izquierda
2- ‘B’ puede moverse solo hacia la derecha
3- Ni ‘A’ ni ‘B’ se cruzan entre sí
Si es posible, escriba «Sí», de lo contrario, «No».
Ejemplos:
Entrada: str1=” #A#B#B# “, str2=” A###B#B ”
Salida: Sí
Explicación:
‘A’ en str1 está a la derecha de ‘A’ en str2 para que ‘A’ de str1 pueda moverse fácilmente hacia la izquierda porque no hay ‘B’ en sus posiciones izquierdas y para la primera ‘B’ en str1 se deja la ‘B’ en str2 para que ‘B’ de str2 pueda moverse fácilmente hacia la derecha porque no hay ‘A ‘ en sus posiciones correctas y es lo mismo para la siguiente ‘B’, por lo que str1 se puede convertir fácilmente en str2.
Entrada :str1=” #A#B# “, str2=” #B#A# ”
Salida :No
Explicación :
Aquí la primera ‘A’ en str1 se deja a la ‘A’ en str2 y según la condición ‘A’ puede ‘ tmover hacia la derecha. entonces str1 no se puede convertir en str2.
Método:
1-La longitud de ambas strings debe ser la misma
2-No. de A y B en ambas strings debe ser igual
3-El orden de A y B en ambas strings debe ser el mismo (por ejemplo: si ‘A’ viene antes que ‘B’ en la segunda string, entonces se debe seguir la misma secuencia cuerda primero)
C++
// C++ Program for above implementation
#include <bits/stdc++.h>
using namespace std;
// Function to check is it possible to convert
// first string into another string or not.
bool isItPossible(string str1, string str2, int m, int n)
{
// To Check Length of Both String is Equal or Not
if (m != n)
return false;
// To Check Frequency of A's and B's are
// equal in both strings or not.
if (count(str1.begin(), str1.end(), 'A') !=
count(str2.begin(), str2.end(), 'A') ||
count(str1.begin(), str1.end(), 'B') !=
count(str2.begin(), str2.end(), 'B'))
return false;
// Start traversing
for (int i = 0; i < m; i++) {
if (str1[i] != '#') {
for (int j = 0; j < n; j++) {
// To Check no two elements cross each other.
if ((str2[j] != str1[i]) && str2[j] != '#')
return false;
if (str2[j] == str1[i]) {
str2[j] = '#';
// To Check Is it Possible to Move
// towards Left or not.
if (str1[i] == 'A' && i < j)
return false;
// To Check Is it Possible to Move
// towards Right or not.
if (str1[i] == 'B' && i > j)
return false;
break;
}
}
}
}
return true;
}
// Drivers code
int main()
{
string str1 = "A#B#";
string str2 = "A##B";
int m = str1.length();
int n = str2.length();
isItPossible(str1, str2, m, n) ? cout << "Yes\n"
: cout << "No\n";
return 0;
}
Java
// Java Program for above implementation
class GFG
{
// Function to check is it possible to convert
// first String into another String or not.
static boolean isItPossible(char[] str1, char[] str2,
int m, int n)
{
// To Check Length of Both String is Equal or Not
if (m != n)
return false;
// To Check Frequency of A's and B's are
// equal in both Strings or not.
if (count(str1, 'A') !=
count(str2, 'A') ||
count(str1, 'B') !=
count(str2, 'B'))
return false;
// Start traversing
for (int i = 0; i < m; i++) {
if (str1[i] != '#') {
for (int j = 0; j < n; j++) {
// To Check no two elements cross each other.
if ((str2[j] != str1[i]) && str2[j] != '#')
return false;
if (str2[j] == str1[i]) {
str2[j] = '#';
// To Check Is it Possible to Move
// towards Left or not.
if (str1[i] == 'A' && i < j)
return false;
// To Check Is it Possible to Move
// towards Right or not.
if (str1[i] == 'B' && i > j)
return false;
break;
}
}
}
}
return true;
}
private static int count(char[] str1, char c) {
int count = 0;
for(char temp : str1) {
if(c == temp)
count++;
}
return count;
}
// Drivers code
public static void main(String[] args)
{
String str1 = "A#B#";
String str2 = "A##B";
int m = str1.length();
int n = str2.length();
System.out.print(isItPossible(str1.toCharArray(), str2.toCharArray(), m, n) ?
"Yes\n":"No\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python Program for above implementation
# Function to check is it possible to convert
# first string into another string or not.
def isItPossible(str1, str2, m, n):
# To Check Length of Both String is Equal or Not
if (m != n):
return False
# To Check Frequency of A's and B's are
# equal in both strings or not.
if str1.count('A') != str2.count('A') \
or str1.count('B') != str2.count('B'):
return False
# Start traversing
for i in range(m):
if (str1[i] != '#'):
for j in range(n):
# To Check no two elements cross each other.
if ((str2[j] != str1[i]) and str2[j] != '#'):
return False
if (str2[j] == str1[i]):
str2[j] = '#'
# To Check Is it Possible to Move
# towards Left or not.
if (str1[i] == 'A' and i < j):
return False
# To Check Is it Possible to Move
# towards Right or not.
if (str1[i] == 'B' and i > j):
return False
break
return True
# Drivers code
str1 = "A#B#"
str2 = "A##B"
m = len(str1)
n = len(str2)
str1 = list(str1)
str2 = list(str2)
if(isItPossible(str1, str2, m, n)):
print("Yes")
else:
print("No")
# This code is contributed by ankush_953
C#
// C# Program for above implementation
using System;
class GFG
{
// Function to check is it possible to convert
// first String into another String or not.
static bool isItPossible(char[] str1, char[] str2,
int m, int n)
{
// To Check Length of Both String is Equal or Not
if (m != n)
return false;
// To Check Frequency of A's and B's are
// equal in both Strings or not.
if (count(str1, 'A') !=
count(str2, 'A') ||
count(str1, 'B') !=
count(str2, 'B'))
return false;
// Start traversing
for (int i = 0; i < m; i++) {
if (str1[i] != '#') {
for (int j = 0; j < n; j++) {
// To Check no two elements cross each other.
if ((str2[j] != str1[i]) && str2[j] != '#')
return false;
if (str2[j] == str1[i]) {
str2[j] = '#';
// To Check Is it Possible to Move
// towards Left or not.
if (str1[i] == 'A' && i < j)
return false;
// To Check Is it Possible to Move
// towards Right or not.
if (str1[i] == 'B' && i > j)
return false;
break;
}
}
}
}
return true;
}
private static int count(char[] str1, char c) {
int count = 0;
foreach(char temp in str1) {
if(c == temp)
count++;
}
return count;
}
// Drivers code
public static void Main(String[] args)
{
String str1 = "A#B#";
String str2 = "A##B";
int m = str1.Length;
int n = str2.Length;
Console.Write(isItPossible(str1.ToCharArray(), str2.ToCharArray(), m, n) ?
"Yes\n":"No\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// js Program for above implementation
function getFreq(string,chr) {
let ans = 0;
for (var i=0; i<string.length;i++) {
if( chr == string.charAt(i))
ans++;
}
return ans;
};
// Function to check is it possible to convert
// first string into another string or not.
function isItPossible(str1, str2, m, n){
// To Check Length of Both String is Equal or Not
if (m != n)
return false;
// To Check Frequency of A's and B's are
// equal in both strings or not.
if (getFreq(str1, 'A') !=
getFreq(str2, 'A') ||
getFreq(str1, 'B') !=
getFreq(str2, 'B'))
return false;
// Start traversing
for (let i = 0; i < m; i++) {
if (str1[i] != '#') {
for (let j = 0; j < n; j++) {
// To Check no two elements cross each other.
if ((str2[j] != str1[i]) && str2[j] != '#')
return false;
if (str2[j] == str1[i]) {
str2 = str2.substr(0,j)+'#'+str2.substr(j+1);
// To Check Is it Possible to Move
// towards Left or not.
if (str1[i] == 'A' && i < j)
return false;
// To Check Is it Possible to Move
// towards Right or not.
if (str1[i] == 'B' && i > j)
return false;
break;
}
}
}
}
return true;
}
// Drivers code
let str1 = "A#B#";
let str2 = "A##B";
let m = str1.length;
let n = str2.length;
isItPossible(str1, str2, m, n) ?document.write( "Yes<br>")
: document.write( "No<br>");
</script>
Producción:
Yes
Complejidad del tiempo: O(n*m)
Espacio Auxiliar: O(n+m)