Dadas dos strings s1 y s2 (letras de llamada en mayúsculas). Compruebe si es posible convertir s1 a s2 realizando las siguientes operaciones.
1. Pon algunas letras minúsculas en mayúsculas.
2. Borra todas las letras minúsculas.
Ejemplos:
Input : s1 = daBcd s2 = ABC Output : yes Explanation : daBcd -> dABCd -> ABC Convert a and b at index 1 and 3 to upper case, delete the rest those are lowercase. We get the string s2. Input : s1 = argaju s2 = RAJ Output : yes Explanation : argaju -> aRgAJu -> RAJ convert index 1, 3 and 4 to uppercase and then delete. All lowercase letters Input : s1 = ABcd s2= BCD Output : NO
Enfoque:
Sea DP i, j 1 si es posible convertir los primeros i caracteres de s1 en j caracteres de s2, de lo contrario, DP i, j = 0. Las observaciones cercanas nos dan dos condiciones para tratar.
Inicialmente DP 0, 0 = 1, si DP i, j = 1, entonces es posible verificar los siguientes conjuntos usando las siguientes condiciones.
1. Si s1[i] en mayúsculas es igual a s2[j] entonces es posible convertir i+1 caracteres de s1 a j+1 caracteres de s2, por lo tanto DP i+1, j+1 =1.
2. Si s1[i] está en minúsculas, es posible eliminar ese elemento y, por lo tanto, los caracteres i+1 se pueden convertir en j caracteres de s2. Por lo tanto , DP i+1, j =1.
Si DP n, m =1, entonces es posible convertir s1 a s2 siguiendo las siguientes condiciones.
A continuación se muestra la ilustración CPP del enfoque anterior.
C++
// cpp program to check if a string can
// be converted to another string by
// performing operations
#include <bits/stdc++.h>
using namespace std;
// function to check if a string can be
// converted to another string by
// performing following operations
bool check(string s1, string s2)
{
// calculates length
int n = s1.length();
int m = s2.length();
bool dp[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = false;
}
}
// mark 1st position as true
dp[0][0] = true;
// traverse for all DPi, j
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
// if possible for to convert i
// characters of s1 to j characters
// of s2
if (dp[i][j]) {
// if upper_case(s1[i])==s2[j]
// is same
if (j < s2.length() &&
(toupper(s1[i]) == s2[j]))
dp[i + 1][j + 1] = true;
// if not upper then deletion is
// possible
if (!isupper(s1[i]))
dp[i + 1][j] = true;
}
}
}
return (dp[n][m]);
}
// driver code
int main()
{
string s1 = "daBcd";
string s2 = "ABC";
if (check(s1, s2))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if a string can
// be converted to another string by
// performing operations
import java.io.*;
class GFG {
// function to check if a string can be
// converted to another string by
// performing following operations
static boolean check(String s1, String s2)
{
// calculates length
int n = s1.length();
int m = s2.length();
boolean dp[][]=new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
dp[i][j] = false;
}
}
// mark 1st position as true
dp[0][0] = true;
// traverse for all DPi, j
for (int i = 0; i < s1.length(); i++)
{
for (int j = 0; j <= s2.length(); j++)
{
// if possible for to convert i
// characters of s1 to j characters
// of s2
if (dp[i][j]) {
// if upper_case(s1[i])==s2[j]
// is same
if (j < s2.length() &&
(Character.toUpperCase(s1.charAt(i)) == s2.charAt(j)))
dp[i + 1][j + 1] = true;
// if not upper then deletion is
// possible
if (!Character.isUpperCase(s1.charAt(i)))
dp[i + 1][j] = true;
}
}
}
return (dp[n][m]);
}
// driver code
public static void main(String args[])
{
String s1 = "daBcd";
String s2 = "ABC";
if (check(s1, s2))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Python3 program to check if a string can
# be converted to another string by
# performing operations
# function to check if a string can be
# converted to another string by
# performing following operations
def check(s1,s2):
# calculates length
n = len(s1)
m = len(s2)
dp=([[False for i in range(m+1)]
for i in range(n+1)])
# mark 1st position as true
dp[0][0] = True
# traverse for all DPi, j
for i in range(len(s1)):
for j in range(len(s2)+1):
# if possible for to convert i
# characters of s1 to j characters
# of s2
if (dp[i][j]):
# if upper_case(s1[i])==s2[j]
# is same
if ((j < len(s2) and
(s1[i].upper()== s2[j]))):
dp[i + 1][j + 1] = True
# if not upper then deletion is
# possible
if (s1[i].isupper()==False):
dp[i + 1][j] = True
return (dp[n][m])
# driver code
if __name__=='__main__':
s1 = "daBcd"
s2 = "ABC"
if (check(s1, s2)):
print("YES")
else:
print("NO")
# this code is contributed by
# sahilshelangia
C#
// C# program to check if a string can
// be converted to another string by
// performing operations
using System;
class GFG
{
// function to check if a string can be
// converted to another string by
// performing following operations
static bool check(string s1, string s2)
{
// calculates length
int n = s1.Length;
int m = s2.Length;
bool[,] dp = new bool[n + 1, m + 1];
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
dp[i, j] = false;
}
}
// mark 1st position as true
dp[0, 0] = true;
// traverse for all DPi, j
for (int i = 0; i < s1.Length; i++)
{
for (int j = 0; j <= s2.Length; j++)
{
// if possible for to convert i
// characters of s1 to j characters
// of s2
if (dp[i, j])
{
// if upper_case(s1[i])==s2[j]
// is same
if (j < s2.Length &&
(Char.ToUpper(s1[i]) == s2[j]))
dp[i + 1, j + 1] = true;
// if not upper then deletion is
// possible
if (!Char.IsUpper(s1[i]))
dp[i + 1, j] = true;
}
}
}
return (dp[n, m]);
}
// Driver Code
public static void Main()
{
string s1 = "daBcd";
string s2 = "ABC";
if (check(s1, s2))
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed
// by ChitraNayal
Javascript
<script>
// Javascript program to check if a string can
// be converted to another string by
// performing operations
// function to check if a string can be
// converted to another string by
// performing following operations
function check(s1,s2)
{
// calculates length
let n = s1.length;
let m = s2.length;
let dp=new Array(n + 1);
for (let i = 0; i <= n; i++)
{
dp[i]=new Array(m+1);
for (let j = 0; j <= m; j++)
{
dp[i][j] = false;
}
}
// mark 1st position as true
dp[0][0] = true;
// traverse for all DPi, j
for (let i = 0; i < s1.length; i++)
{
for (let j = 0; j <= s2.length; j++)
{
// if possible for to convert i
// characters of s1 to j characters
// of s2
if (dp[i][j]) {
// if upper_case(s1[i])==s2[j]
// is same
if (j < s2.length &&
(s1[i].toUpperCase() == s2[j]))
dp[i + 1][j + 1] = true;
// if not upper then deletion is
// possible
if (!(s1[i] == s1[i].toUpperCase()))
dp[i + 1][j] = true;
}
}
}
return (dp[n][m]);
}
// driver code
let s1 = "daBcd";
let s2 = "ABC";
if (check(s1, s2))
document.write("YES");
else
document.write("NO");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
YES
Complejidad de tiempo : O(N*M) donde N y M son las longitudes de las strings.
Espacio Auxiliar : O(N*M)