Dadas dos strings S1 y S2 (todos los caracteres están en minúsculas). La tarea es verificar si S2 se puede formar a partir de S1 usando las restricciones dadas:
1. Los caracteres de S2 están en S1 si hay dos ‘a’ en S2, entonces S1 debería tener dos ‘a’ también.
2. Si algún carácter de S2 no está presente en S1, verifique si los dos caracteres ASCII anteriores están presentes en S1. por ejemplo, si ‘e’ está en S2 y no en S1, entonces ‘c’ y ‘d’ pueden usarse desde S1 para hacer ‘e’.
Nota: Todos los caracteres de S1 solo se pueden usar una vez.
Ejemplos:
Entrada: S= abbat, W= cat
Salida: SÍ
‘c’ se forma a partir de ‘a’ y ‘b’, ‘a’ y ‘t’ están presentes en S1.Entrada: S= abbt, W= cat
Salida: NO
se forma ‘c’ a partir de ‘a’ y ‘b’, pero para formar el siguiente carácter
‘a’ en S2, no queda más ‘a’ sin usar en S1.
Enfoque: el problema anterior se puede resolver utilizando hashing. El recuento de todos los caracteres en S1 se almacena en una tabla hash. Recorra la string y verifique si el carácter en S2 está allí en la tabla hash, reduzca el recuento de ese carácter en particular en la tabla hash. Si el carácter no está en la tabla hash, verifique si los dos caracteres ASCII anteriores están en la tabla hash, luego reduzca la cuenta de los dos caracteres ASCII anteriores en la tabla hash. Si todos los caracteres se pueden formar a partir de S1 utilizando las restricciones dadas, la string S2 se puede formar a partir de S1; de lo contrario, no se puede formar.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to Check if a given
// string can be formed from another
// string using given constraints
#include <bits/stdc++.h>
using namespace std;
// Function to check if S2 can be formed of S1
bool check(string S1, string S2)
{
// length of strings
int n1 = S1.size();
int n2 = S2.size();
// hash-table to store count
unordered_map<int, int> mp;
// store count of each character
for (int i = 0; i < n1; i++) {
mp[S1[i]]++;
}
// traverse and check for every character
for (int i = 0; i < n2; i++) {
// if the character of s2 is present in s1
if (mp[S2[i]]) {
mp[S2[i]]--;
}
// if the character of s2 is not present in
// S1, then check if previous two ASCII characters
// are present in S1
else if (mp[S2[i] - 1] && mp[S2[i] - 2]) {
mp[S2[i] - 1]--;
mp[S2[i] - 2]--;
}
else {
return false;
}
}
return true;
}
// Driver Code
int main()
{
string S1 = "abbat";
string S2 = "cat";
// Calling function to check
if (check(S1, S2))
cout << "YES";
else
cout << "NO";
}
Java
// JAVA program to Check if a given
// String can be formed from another
// String using given constraints
import java.util.*;
class GFG
{
// Function to check if S2 can be formed of S1
static boolean check(String S1, String S2)
{
// length of Strings
int n1 = S1.length();
int n2 = S2.length();
// hash-table to store count
HashMap<Integer,Integer> mp =
new HashMap<Integer,Integer>();
// store count of each character
for (int i = 0; i < n1; i++)
{
if(mp.containsKey((int)S1.charAt(i)))
{
mp.put((int)S1.charAt(i),
mp.get((int)S1.charAt(i)) + 1);
}
else
{
mp.put((int)S1.charAt(i), 1);
}
}
// traverse and check for every character
for (int i = 0; i < n2; i++)
{
// if the character of s2 is present in s1
if(mp.containsKey((int)S2.charAt(i)))
{
mp.put((int)S2.charAt(i),
mp.get((int)S2.charAt(i)) - 1);
}
// if the character of s2 is not present in
// S1, then check if previous two ASCII characters
// are present in S1
else if (mp.containsKey(S2.charAt(i)-1) &&
mp.containsKey(S2.charAt(i)-2))
{
mp.put((S2.charAt(i) - 1),
mp.get(S2.charAt(i) - 1) - 1);
mp.put((S2.charAt(i) - 2),
mp.get(S2.charAt(i) - 2) - 1);
}
else
{
return false;
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
String S1 = "abbat";
String S2 = "cat";
// Calling function to check
if (check(S1, S2))
System.out.print("YES");
else
System.out.print("NO");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to Check if a given string
# can be formed from another string using
# given constraints
from collections import defaultdict
# Function to check if S2 can
# be formed of S1
def check(S1, S2):
# length of strings
n1 = len(S1)
n2 = len(S2)
# hash-table to store count
mp = defaultdict(lambda:0)
# store count of each character
for i in range(0, n1):
mp[S1[i]] += 1
# traverse and check for every character
for i in range(0, n2):
# if the character of s2 is
# present in s1
if mp[S2[i]]:
mp[S2[i]] -= 1
# if the character of s2 is not present
# in S1, then check if previous two ASCII
# characters are present in S1
elif (mp[chr(ord(S2[i]) - 1)] and
mp[chr(ord(S2[i]) - 2)]):
mp[chr(ord(S2[i]) - 1)] -= 1
mp[chr(ord(S2[i]) - 2)] -= 1
else:
return False
return True
# Driver Code
if __name__ == "__main__":
S1 = "abbat"
S2 = "cat"
# Calling function to check
if check(S1, S2):
print("YES")
else:
print("NO")
# This code is contributed by Rituraj Jain
C#
// C# program to Check if a given
// String can be formed from another
// String using given constraints
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if S2 can be formed of S1
static bool check(String S1, String S2)
{
// length of Strings
int n1 = S1.Length;
int n2 = S2.Length;
// hash-table to store count
Dictionary<int,int> mp =
new Dictionary<int,int>();
// store count of each character
for (int i = 0; i < n1; i++)
{
if(mp.ContainsKey((int)S1[i]))
{
mp[(int)S1[i]] = mp[(int)S1[i]] + 1;
}
else
{
mp.Add((int)S1[i], 1);
}
}
// traverse and check for every character
for (int i = 0; i < n2; i++)
{
// if the character of s2 is present in s1
if(mp.ContainsKey((int)S2[i]))
{
mp[(int)S2[i]] = mp[(int)S2[i]] - 1;
}
// if the character of s2 is not present in
// S1, then check if previous two ASCII characters
// are present in S1
else if (mp.ContainsKey(S2[i] - 1) &&
mp.ContainsKey(S2[i] - 2))
{
mp[S2[i] - 1] = mp[S2[i] - 1] - 1;
mp[S2[i] - 2] = mp[S2[i] - 2] - 1;
}
else
{
return false;
}
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
String S1 = "abbat";
String S2 = "cat";
// Calling function to check
if (check(S1, S2))
Console.Write("YES");
else
Console.Write("NO");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to Check if a given
// String can be formed from another
// String using given constraints
// Function to check if S2 can be formed of S1
function check(S1, S2)
{
// Length of Strings
var n1 = S1.length;
var n2 = S2.length;
// hash-table to store count
var mp = {};
// Store count of each character
for(var i = 0; i < n1; i++)
{
if (mp.hasOwnProperty(S1[i]))
{
mp[S1[i]] = mp[S1[i]] + 1;
}
else
{
mp[S1[i]] = 1;
}
}
// Traverse and check for every character
for(var i = 0; i < n2; i++)
{
// If the character of s2 is present in s1
if (mp.hasOwnProperty(S2[i]))
{
mp[S2[i]] = mp[S2[i]] - 1;
}
// If the character of s2 is not present
// in S1, then check if previous two ASCII
// characters are present in S1
else if (mp.hasOwnProperty(
String.fromCharCode(S2[i].charCodeAt(0) - 1)) &&
mp.hasOwnProperty(
String.fromCharCode(S2[i].charCodeAt(0) - 2)))
{
mp[String.fromCharCode(
S2[i].charCodeAt(0) - 1)] =
mp[String.fromCharCode(
S2[i].charCodeAt(0) - 1)] - 1;
mp[String.fromCharCode(
S2[i].charCodeAt(0) - 2)] =
mp[String.fromCharCode(
S2[i].charCodeAt(0) - 2)] - 1;
}
else
{
return false;
}
}
return true;
}
// Driver Code
var S1 = "abbat";
var S2 = "cat";
// Calling function to check
if (check(S1, S2))
document.write("YES");
else
document.write("NO");
// This code is contributed by rdtank
</script>
YES
Complejidad de tiempo: O (m + n), donde m es la longitud de la string s1 y n es la longitud de la string s2.
Espacio auxiliar: O(m), donde m es la longitud de la string s1.
Publicación traducida automáticamente
Artículo escrito por MahimaSharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA