Comprobar si dos strings dadas son isomorfas entre sí | Conjunto 2 (Usando STL)

Dadas dos strings str1 y str2 , la tarea es verificar si las dos strings son isomorfas entre sí.

Dos strings , str1 y str2 , se denominan isomorfas si existe un mapeo uno a uno posible para cada carácter de str1 con cada carácter de str2 y todas las apariciones de cada carácter en ‘str1’ se asignan al mismo carácter en ‘str2’.

Ejemplos: 

Entrada:  str1 = “aab”, str2 = “xxy”
Salida: Verdadero
Explicación: ‘a’ se asigna a ‘x’ y ‘b’ se asigna a ‘y’.

Entrada:  str1 = “aab”, str2 = “xyz”
Salida: Falso
Explicación: Una ocurrencia de ‘a’ en str1 tiene ‘x’ en str2 y otra ocurrencia de ‘a’ tiene ‘y’. 

Enfoque : el enfoque basado en el recuento de frecuencias y el diccionario se mencionan en la publicación anterior . Aquí discutiremos la solución usando STL . La idea de esto se menciona a continuación:

Use la estructura de datos del mapa desordenada para propósitos de hash usando el carácter de str1 como la clave y la diferencia entre el valor ASCII de los dos caracteres en el mismo índice que el valor. 
Si el mismo carácter se repite, verifique si el valor hash previamente coincide o no, lo que confirma si un carácter está asignado a un solo carácter. 

Siga los pasos a continuación para resolver el problema:

• Compruebe si el tamaño de str1 es el mismo que str2 o no,  
• Si no, devuelve falso.
• Ahora declare un mapa desordenado y comience a iterar desde el índice 0 de str1 .
• Para cada carácter, compruebe si el carácter actual ya apareció o no
  • De lo contrario, agregue el par clave-valor como se mencionó anteriormente.
  • De lo contrario, verifique si map[str1[curr_index]] = str1[curr_index] – str2[curr_index] . Si no es igual, devuelve falso.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// This function returns true if
// str1 and str2 are isomorphic
bool areIsomorphic(string str1, string str2)
{
    // Unordered map to store the
    // Hash value for each string
    unordered_map<char, int> fre;
 
    int size1 = str1.size();
    int size2 = str2.size();
 
    // Check whether size equals or not,
    // if not then isomorphism
    // can't be achieved
    if (size1 != size2)
        return false;
 
    for (int i = 0; i < size1; i++) {
 
        // Check whether current character
        // already hashed or not
        if (fre.find(str1[i]) == fre.end()) {
 
            // If not then assign
            // hash value to it
            fre[str1[i]] = str1[i] - str2[i];
        }
 
        // If already hashed then compare
        // with its current hashed value
        else if (fre[str1[i]]
                 != (str1[i] - str2[i])) {
            return false;
        }
    }
    return true;
}
 
// Driver program
int main()
{
    string s1 = "aab";
    string s2 = "xxy";
 
    // Calling function
    bool ans = areIsomorphic(s1, s2);
    if (ans)
        cout << "True";
    else
        cout << "False";
    return 0;
}

// Java code to implement the approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // This function returns true if
  // str1 and str2 are isomorphic
  public static boolean areIsomorphic(String str1,
                                      String str2)
  {
     
    // Unordered map to store the
    // Hash value for each string
    HashMap<Character, Integer> fre = new HashMap<>();
 
    int size1 = str1.length();
    int size2 = str2.length();
 
    // Check whether size equals or not,
    // if not then isomorphism
    // can't be achieved
    if (size1 != size2)
      return false;
 
    for (int i = 0; i < size1; i++) {
 
      // Check whether current character
      // already hashed or not
      if (fre.get(str1.charAt(i)) == null) {
 
        // If not then assign
        // hash value to it
        fre.put(
          str1.charAt(i),
          (int)(str1.charAt(i) - str2.charAt(i)));
      }
 
      // If already hashed then compare
      // with its current hashed value
      else if (fre.get(str1.charAt(i))
               != (int)((str1.charAt(i)
                         - str2.charAt(i)))) {
        return false;
      }
    }
    return true;
  }
  public static void main(String[] args)
  {
    String s1 = "aab";
    String s2 = "xxy";
 
    // Calling function
    boolean ans = areIsomorphic(s1, s2);
    if (ans != false)
      System.out.print("True");
    else
      System.out.print("False");
  }
}
 
// This code is contributed by Rohit Pradhan

# Python3 code for the above approach
 
# This function returns true if
# str1 and str2 are isomorphic
def areIsomorphic(str1, str2):
 
    # Unordered map to store the
    # Hash value for each string
    fre = dict()
 
    size1 = len(str1)
    size2 = len(str2)
 
    # Check whether size equals or not
    # if not then isomorphism
    # can't be achieved
    if size1 != size2:
        return False
 
    for i in range(size1):
        # Check whether current character
        # already hashed or not
        if str1[i] not in fre:
            # If not then assign
            # hash value to it
            fre[str1[i]] = ord(str1[i]) - ord(str2[i])
 
        # If already hashed then compare
        # with its current hashed value
        else:
            if fre[str1[i]] != (ord(str1[i]) - ord(str2[i])):
                return False
 
    return True
 
# Driver code
s1 = "aab"
s2 = "xxy"
 
# function call
print(areIsomorphic(s1, s2))
 
 
# this code is contributed by phasing17

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // This function returns true if
  // str1 and str2 are isomorphic
  static bool areIsomorphic(String str1, String str2)
  {
 
    // Unordered map to store the
    // Hash value for each string
    Dictionary<char, int> fre = new Dictionary<char, int>();
 
    int size1 = str1.Length;
    int size2 = str2.Length;
 
    // Check whether size equals or not,
    // if not then isomorphism
    // can't be achieved
    if (size1 != size2){
      return false;
    }
 
    for (int i = 0 ; i < size1 ; i++) {
 
      // Check whether current character
      // already hashed or not
      if (!fre.ContainsKey(str1[i])) {
 
        // If not then assign
        // hash value to it
        fre.Add(str1[i], ((int)str1[i] - (int)str2[i]));
      }
 
      // If already hashed then compare
      // with its current hashed value
      else if (fre[str1[i]] != ((int)str1[i] - (int)str2[i])){
        return false;
      }
    }
    return true;
  }
 
  // Driver Code
  public static void Main(string[] args){
 
    String s1 = "aab";
    String s2 = "xxy";
 
    // Calling function
    bool ans = areIsomorphic(s1, s2);
    if (ans){
      Console.WriteLine("True");
    }else{
      Console.WriteLine("False");
    }
 
  }
}
 
// This code is contributed by entertain2022.

<script>
// JS code to implement the approach
 
// This function returns true if
// str1 and str2 are isomorphic
function areIsomorphic(str1, str2)
{
 
    // Unordered map to store the
    // Hash value for each string
    var fre = {};
 
    var size1 = str1.length;
    var size2 = str2.length;
 
    // Check whether size equals or not,
    // if not then isomorphism
    // can't be achieved
    if (size1 != size2)
        return false;
 
    for (var i = 0; i < size1; i++) {
 
        // Check whether current character
        // already hashed or not
        if (fre.hasOwnProperty(str1[i])) {
 
            // If not then assign
            // hash value to it
            fre[str1[i]] = str1[i] - str2[i];
        }
 
        // If already hashed then compare
        // with its current hashed value
        else if (fre[str1[i]] != (str1[i] - str2[i])) {
            return false;
        }
    }
    return true;
}
 
// Driver program
var s1 = "aab";
var s2 = "xxy";
 
// Calling function
var ans = areIsomorphic(s1, s2);
if (ans)
    document.write("True");
else
    document.write("False");
 
// This code was contributed by phasing17
</script>

True

Complejidad de tiempo: O(N) donde N es el tamaño de las strings
Espacio auxiliar: O(N)