Dadas dos strings s1 y s2 , la tarea es verificar si los caracteres de la primera string se pueden asignar con el carácter de la segunda string, de modo que si un carácter ch1 se asigna con algún carácter ch2 , todas las ocurrencias de ch1 solo se asignarán con ch2 para ambas strings.
Ejemplos:
Entrada: s1 = “axx”, s2 = “cbc”
Salida: Sí
, ‘a’ en s1 se puede asignar a ‘b’ en s2
y ‘x’ en s1 se puede asignar a ‘c’ en s2.Entrada: s1 = “a”, s2 = “df”
Salida: No
Enfoque: si las longitudes de ambas strings no son iguales, las strings no se pueden mapear; de lo contrario, cree dos arrays de frecuencia freq1 [] y freq2 [] que almacenarán las frecuencias de todos los caracteres de las strings dadas s1 y s2 respectivamente. Ahora, para cada valor distinto de cero en freq1[] encuentre un valor igual en freq2[] . Si todos los valores distintos de cero de freq1[] se pueden asignar a algún valor en freq2[], entonces la respuesta es posible, de lo contrario 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;
#define MAX 26
// Function that returns true if the mapping is possible
bool canBeMapped(string s1, int l1, string s2, int l2)
{
// Both the strings are of un-equal lengths
if (l1 != l2)
return false;
// To store the frequencies of the
// characters in both the string
int freq1[MAX] = { 0 };
int freq2[MAX] = { 0 };
// Update frequencies of the characters
for (int i = 0; i < l1; i++)
freq1[s1[i] - 'a']++;
for (int i = 0; i < l2; i++)
freq2[s2[i] - 'a']++;
// For every character of s1
for (int i = 0; i < MAX; i++) {
// If current character is
// not present in s1
if (freq1[i] == 0)
continue;
bool found = false;
// Find a character in s2 that has frequency
// equal to the current character's
// frequency in s1
for (int j = 0; j < MAX; j++) {
// If such character is found
if (freq1[i] == freq2[j]) {
// Set the frequency to -1 so that
// it doesn't get picked again
freq2[j] = -1;
// Set found to true
found = true;
break;
}
}
// If there is no character in s2
// that could be mapped to the
// current character in s1
if (!found)
return false;
}
return true;
}
// Driver code
int main()
{
string s1 = "axx";
string s2 = "cbc";
int l1 = s1.length();
int l2 = s2.length();
if (canBeMapped(s1, l1, s2, l2))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 26;
// Function that returns true if the mapping is possible
public static boolean canBeMapped(String s1, int l1,
String s2, int l2)
{
// Both the strings are of un-equal lengths
if (l1 != l2)
return false;
// To store the frequencies of the
// characters in both the string
int[] freq1 = new int[MAX];
int[] freq2 = new int[MAX];
// Update frequencies of the characters
for (int i = 0; i < l1; i++)
freq1[s1.charAt(i) - 'a']++;
for (int i = 0; i < l2; i++)
freq2[s2.charAt(i) - 'a']++;
// For every character of s1
for (int i = 0; i < MAX; i++) {
// If current character is
// not present in s1
if (freq1[i] == 0)
continue;
boolean found = false;
// Find a character in s2 that has frequency
// equal to the current character's
// frequency in s1
for (int j = 0; j < MAX; j++)
{
// If such character is found
if (freq1[i] == freq2[j])
{
// Set the frequency to -1 so that
// it doesn't get picked again
freq2[j] = -1;
// Set found to true
found = true;
break;
}
}
// If there is no character in s2
// that could be mapped to the
// current character in s1
if (!found)
return false;
}
return true;
}
// Driver code
public static void main(String[] args)
{
String s1 = "axx";
String s2 = "cbc";
int l1 = s1.length();
int l2 = s2.length();
if (canBeMapped(s1, l1, s2, l2))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python 3 implementation of the approach
MAX = 26
# Function that returns true if the mapping is possible
def canBeMapped(s1, l1, s2, l2):
# Both the strings are of un-equal lengths
if (l1 != l2):
return False
# To store the frequencies of the
# characters in both the string
freq1 = [0 for i in range(MAX)]
freq2 = [0 for i in range(MAX)]
# Update frequencies of the characters
for i in range(l1):
freq1[ord(s1[i]) - ord('a')] += 1
for i in range(l2):
freq2[ord(s2[i]) - ord('a')] += 1
# For every character of s1
for i in range(MAX):
# If current character is
# not present in s1
if (freq1[i] == 0):
continue
found = False
# Find a character in s2 that has frequency
# equal to the current character's
# frequency in s1
for j in range(MAX):
# If such character is found
if (freq1[i] == freq2[j]):
# Set the frequency to -1 so that
# it doesn't get picked again
freq2[j] = -1
# Set found to true
found = True
break
# If there is no character in s2
# that could be mapped to the
# current character in s1
if (found==False):
return False
return True
# Driver code
if __name__ == '__main__':
s1 = "axx"
s2 = "cbc"
l1 = len(s1)
l2 = len(s2)
if (canBeMapped(s1, l1, s2, l2)):
print("Yes")
else:
print("No")
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 26;
// Function that returns true
// if the mapping is possible
public static Boolean canBeMapped(String s1, int l1,
String s2, int l2)
{
// Both the strings are of un-equal lengths
if (l1 != l2)
return false;
// To store the frequencies of the
// characters in both the string
int[] freq1 = new int[MAX];
int[] freq2 = new int[MAX];
// Update frequencies of the characters
for (int i = 0; i < l1; i++)
freq1[s1[i] - 'a']++;
for (int i = 0; i < l2; i++)
freq2[s2[i] - 'a']++;
// For every character of s1
for (int i = 0; i < MAX; i++)
{
// If current character is
// not present in s1
if (freq1[i] == 0)
continue;
Boolean found = false;
// Find a character in s2 that has frequency
// equal to the current character's
// frequency in s1
for (int j = 0; j < MAX; j++)
{
// If such character is found
if (freq1[i] == freq2[j])
{
// Set the frequency to -1 so that
// it doesn't get picked again
freq2[j] = -1;
// Set found to true
found = true;
break;
}
}
// If there is no character in s2
// that could be mapped to the
// current character in s1
if (!found)
return false;
}
return true;
}
// Driver code
public static void Main(String[] args)
{
String s1 = "axx";
String s2 = "cbc";
int l1 = s1.Length;
int l2 = s2.Length;
if (canBeMapped(s1, l1, s2, l2))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed
// by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
var MAX = 26;
// Function that returns true if the mapping is possible
function canBeMapped(s1, l1, s2, l2)
{
// Both the strings are of un-equal lengths
if (l1 != l2)
return false;
// To store the frequencies of the
// characters in both the string
var freq1 = Array(MAX).fill(0);
var freq2 = Array(MAX).fill(0);
// Update frequencies of the characters
for (var i = 0; i < l1; i++)
freq1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
for (var i = 0; i < l2; i++)
freq2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// For every character of s1
for (var i = 0; i < MAX; i++) {
// If current character is
// not present in s1
if (freq1[i] == 0)
continue;
var found = false;
// Find a character in s2 that has frequency
// equal to the current character's
// frequency in s1
for (var j = 0; j < MAX; j++) {
// If such character is found
if (freq1[i] == freq2[j]) {
// Set the frequency to -1 so that
// it doesn't get picked again
freq2[j] = -1;
// Set found to true
found = true;
break;
}
}
// If there is no character in s2
// that could be mapped to the
// current character in s1
if (!found)
return false;
}
return true;
}
// Driver code
var s1 = "axx";
var s2 = "cbc";
var l1 = s1.length;
var l2 = s2.length;
if (canBeMapped(s1, l1, s2, l2))
document.write( "Yes");
else
document.write( "No");
</script>
Producción:
Yes