Comprobar si dos strings dadas son isomorfas entre sí – Part 1

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: 

C++

// C++ program to check if two strings are isomorphic
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHARS 256
 
// This function returns true if str1 and str2 are isomorphic
bool areIsomorphic(string str1, string str2)
{
 
    int m = str1.length(), n = str2.length();
 
    // Length of both strings must be same for one to one
    // correspondence
    if (m != n)
        return false;
 
    // To mark visited characters in str2
    bool marked[MAX_CHARS] = { false };
 
    // To store mapping of every character from str1 to
    // that of str2. Initialize all entries of map as -1.
    int map[MAX_CHARS];
    memset(map, -1, sizeof(map));
 
    // Process all characters one by on
    for (int i = 0; i < n; i++) {
        // If current character of str1 is seen first
        // time in it.
        if (map[str1[i]] == -1) {
            // If current character of str2 is already
            // seen, one to one mapping not possible
            if (marked[str2[i]] == true)
                return false;
 
            // Mark current character of str2 as visited
            marked[str2[i]] = true;
 
            // Store mapping of current characters
            map[str1[i]] = str2[i];
        }
 
        // If this is not first appearance of current
        // character in str1, then check if previous
        // appearance mapped to same character of str2
        else if (map[str1[i]] != str2[i])
            return false;
    }
 
    return true;
}
 
// Driver program
int main()
{
    cout << areIsomorphic("aab", "xxy") << endl;
    cout << areIsomorphic("aab", "xyz") << endl;
    return 0;
}

Java

// Java program to check if two strings are isomorphic
import java.io.*;
import java.util.*;
class Isomorphic {
    static int size = 256;
 
    // Function returns true if str1 and str2 are isomorphic
    static boolean areIsomorphic(String str1, String str2)
    {
        int m = str1.length();
        int n = str2.length();
 
        // Length of both strings must be same for one to
        // one correspondence
        if (m != n)
            return false;
 
        // To mark visited characters in str2
        Boolean[] marked = new Boolean[size];
        Arrays.fill(marked, Boolean.FALSE);
 
        // To store mapping of every character from str1 to
        // that of str2. Initialize all entries of map as
        // -1.
        int[] map = new int[size];
        Arrays.fill(map, -1);
 
        // Process all characters one by on
        for (int i = 0; i < n; i++) {
            // If current character of str1 is seen first
            // time in it.
            if (map[str1.charAt(i)] == -1) {
                // If current character of str2 is already
                // seen, one to one mapping not possible
                if (marked[str2.charAt(i)] == true)
                    return false;
 
                // Mark current character of str2 as visited
                marked[str2.charAt(i)] = true;
 
                // Store mapping of current characters
                map[str1.charAt(i)] = str2.charAt(i);
            }
 
            // If this is not first appearance of current
            // character in str1, then check if previous
            // appearance mapped to same character of str2
            else if (map[str1.charAt(i)] != str2.charAt(i))
                return false;
        }
 
        return true;
    }
    // driver program
    public static void main(String[] args)
    {
        boolean res = areIsomorphic("aab", "xxy");
        System.out.println(res);
 
        res = areIsomorphic("aab", "xyz");
        System.out.println(res);
    }
}

Python

# Python program to check if two strings are isomorphic
MAX_CHARS = 256
 
# This function returns true if str1 and str2 are isomorphic
 
 
def areIsomorphic(string1, string2):
    m = len(string1)
    n = len(string2)
 
    # Length of both strings must be same for one to one
    # correspondence
    if m != n:
        return False
 
    # To mark visited characters in str2
    marked = [False] * MAX_CHARS
 
    # To store mapping of every character from str1 to
    # that of str2. Initialize all entries of map as -1
    map = [-1] * MAX_CHARS
 
    # Process all characters one by one
    for i in xrange(n):
 
        # if current character of str1 is seen first
        # time in it.
        if map[ord(string1[i])] == -1:
 
            # if current character of st2 is already
            # seen, one to one mapping not possible
            if marked[ord(string2[i])] == True:
                return False
 
            # Mark current character of str2 as visited
            marked[ord(string2[i])] = True
 
            # Store mapping of current characters
            map[ord(string1[i])] = string2[i]
 
        # If this is not first appearance of current
        # character in str1, then check if previous
        # appearance mapped to same character of str2
        elif map[ord(string1[i])] != string2[i]:
            return False
 
    return True
 
 
# Driver program
print areIsomorphic("aab", "xxy")
print areIsomorphic("aab", "xyz")
# This code is contributed by Bhavya Jain

C#

// C# program to check if two
// strings are isomorphic
using System;
 
class GFG {
 
    static int size = 256;
 
    // Function returns true if str1
    // and str2 are isomorphic
    static bool areIsomorphic(String str1, String str2)
    {
 
        int m = str1.Length;
        int n = str2.Length;
 
        // Length of both strings must be same
        // for one to one correspondence
        if (m != n)
            return false;
 
        // To mark visited characters in str2
        bool[] marked = new bool[size];
 
        for (int i = 0; i < size; i++)
            marked[i] = false;
 
        // To store mapping of every character
        // from str1 to that of str2 and
        // Initialize all entries of map as -1.
        int[] map = new int[size];
 
        for (int i = 0; i < size; i++)
            map[i] = -1;
 
        // Process all characters one by on
        for (int i = 0; i < n; i++) {
 
            // If current character of str1 is
            // seen first time in it.
            if (map[str1[i]] == -1) {
 
                // If current character of str2
                // is already seen, one to
                // one mapping not possible
                if (marked[str2[i]] == true)
                    return false;
 
                // Mark current character of
                // str2 as visited
                marked[str2[i]] = true;
 
                // Store mapping of current characters
                map[str1[i]] = str2[i];
            }
 
            // If this is not first appearance of current
            // character in str1, then check if previous
            // appearance mapped to same character of str2
            else if (map[str1[i]] != str2[i])
                return false;
        }
 
        return true;
    }
 
    // Driver code
    public static void Main()
    {
        bool res = areIsomorphic("aab", "xxy");
        Console.WriteLine(res);
 
        res = areIsomorphic("aab", "xyz");
        Console.WriteLine(res);
    }
}
 
// This code is contributed by Sam007.

Javascript

<script>
    // Javascript program to check if two
    // strings are isomorphic
     
    let size = 256;
      
    // Function returns true if str1
    // and str2 are isomorphic
    function areIsomorphic(str1, str2)
    {
          
        let m = str1.length;
        let n = str2.length;
          
        // Length of both strings must be same
        // for one to one correspondence
        if(m != n)
            return false;
              
        // To mark visited characters in str2
        let marked = new Array(size);
          
        for(let i = 0; i < size; i++)
            marked[i]= false;
          
          
        // To store mapping of every character
        // from str1 to that of str2 and
        // Initialize all entries of map as -1.
        let map = new Array(size);
        map.fill(0);
          
        for(let i = 0; i < size; i++)
            map[i]= -1;
      
        // Process all characters one by on
        for (let i = 0; i < n; i++)
        {
              
            // If current character of str1 is
            // seen first time in it.
            if (map[str1[i].charCodeAt()] == -1)
            {
                  
                // If current character of str2
                // is already seen, one to
                // one mapping not possible
                if (marked[str2[i].charCodeAt()] == true)
                    return false;
  
                // Mark current character of
                // str2 as visited
                marked[str2[i].charCodeAt()] = true;
  
                // Store mapping of current characters
                map[str1[i].charCodeAt()] = str2[i].charCodeAt();
            }
  
            // If this is not first appearance of current
            // character in str1, then check if previous
            // appearance mapped to same character of str2
            else if (map[str1[i].charCodeAt()] != str2[i].charCodeAt())
                return 0;
        }
  
        return 1;
    }
     
    let res = areIsomorphic("aab", "xxy");
    document.write(res + "</br>");
 
    res = areIsomorphic("aab", "xyz");
    document.write(res);
     
    // This code is contributed by decode2207.
</script>

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHARS 26
 
// This function returns true if
// str1 and str2 are isomorphic
bool areIsomorphic(string str1, string str2)
{
    int n = str1.length(), m = str2.length();
 
    // Length of both strings must be
    // same for one to one
    // correspondence
    if (n != m)
        return false;
 
    // For counting the previous appearances of character in
    // both the strings
    int count[MAX_CHARS] = { 0 };
    int dcount[MAX_CHARS] = { 0 };
 
    // Process all characters one by one
    for (int i = 0; i < n; i++) {
        count[str1[i] - 'a']++;
        dcount[str2[i] - 'a']++;
    }
        // For string to be isomorphic the previous counts
        // of appearances of
        // current character in both string must be same if
        // it is not same we return false.
   
   
          //before it was not working for the test case mentioned below(wrong output)
          // str1 = "aba" , str2 = "xyy"
      for(int i= 0; i < n; i++) {
        if (count[str1[i] - 'a'] != dcount[str2[i] - 'a']) {
            return false;
        }
    }
    return true;
}
 
// Driver Code
int main()
{
    cout << areIsomorphic("aab", "xxy") << endl;
    cout << areIsomorphic("aba", "xyy") << endl;
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    static final int CHAR = 26;
 
    // This function returns true if
    // str1 and str2 are isomorphic
    static boolean isoMorphic(String str1, String str2)
    {
        int n = str1.length();
        int m = str2.length();
 
        // Length of both strings must be
        // same for one to one
        // correspondence
        if (n != m)
            return false;
 
        // For counting the previous appearances
        // of character in both the strings
        int[] countChars1 = new int[CHAR];
        int[] countChars2 = new int[CHAR];
 
        // Process all characters one by one
        for (int i = 0; i < n; i++) {
            countChars1[str1.charAt(i) - 'a']++;
            countChars2[str2.charAt(i) - 'a']++;
        }
            // For string to be isomorphic the
            // previous counts of appearances of
            // current character in both string
            // must be same if it is not same we
            // return false.
       
          //before it was not working for the test case mentioned below(wrong output)
          // str1 = "aba" , str2 = "xyy"
          for(int i= 0; i < n; i++) {
            if (countChars1[str1.charAt(i) - 'a']
                != countChars2[str2.charAt(i) - 'a']) {
                return false;
            }
        }
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        System.out.println(isoMorphic("aab", "xxy") ? 1
                                                    : 0);
        System.out.println(isoMorphic("aba", "xyy") ? 1
                                                    : 0);
    }
}
 
// This code is contributed by rohansharma1808

Python3

# Python3 program for the above approach
CHAR = 26
 
# This function returns true if
# str1 and str2 are isomorphic
def isoMorphic(str1, str2):
    n = len(str1)
    m = len(str2)
     
    # Length of both strings must be
    # same for one to one correspondence
    if n != m:
        return False
         
     
    # for counting the previous appearances of character
    # in both the strings
    countChars1 = [0] * CHAR
    countChars2 = [0] * CHAR
     
    # Process all characters one by one
    for i in range(n):
        countChars1[ord(str1[i]) - ord('a')] += 1
        countChars2[ord(str2[i]) - ord('a')] += 1
     
    # For string to be isomorphice the
    # previous counts of appearances of
    # current character in both string
    # must be same if it is not same
    # we return false
    for i in range(n):
        if countChars1[ord(str1[i]) - ord('a')] != countChars2[ord(str2[i]) - ord('a')]:
            return False
     
    return True
 
# Driver Code
print(int(isoMorphic("aab", "xxy")))
print(int(isoMorphic("aab", "xyz")))
 
# This code is contributed by phasing17

C#

// C# program for the above approach
using System;
class GFG {
 
    static int CHAR = 26;
 
    // This function returns true if
    // str1 and str2 are isomorphic
    static bool isoMorphic(string str1, string str2)
    {
        int n = str1.Length;
        int m = str2.Length;
 
        // Length of both strings must be
        // same for one to one
        // correspondence
        if (n != m)
            return false;
 
        // For counting the previous appearances
        // of character in both the strings
        int[] countChars1 = new int[CHAR];
        int[] countChars2 = new int[CHAR];
 
        // Process all characters one by one
        for (int i = 0; i < n; i++) {
            countChars1[str1[i] - 'a']++;
            countChars2[str2[i] - 'a']++;
        }
            // For string to be isomorphic the
            // previous counts of appearances of
            // current character in both string
            // must be same if it is not same we
            // return false.
       
          //before it was not working for the test case mentioned below(wrong output)
          // str1 = "aba" , str2 = "xyy"
       for (int i = 0; i < n; i++) {
            if (countChars1[str1[i] - 'a']
                != countChars2[str2[i] - 'a']) {
                return false;
            }
        }
        return true;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        Console.WriteLine(isoMorphic("aab", "xxy") ? 1 : 0);
        Console.WriteLine(isoMorphic("aab", "xyz") ? 1 : 0);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>   
    // Javascript program for the above approach
     
    let CHAR = 26;
  
    // This function returns true if
    // str1 and str2 are isomorphic
    function isoMorphic(str1, str2)
    {
        let n = str1.length;
        let m = str2.length;
 
        // Length of both strings must be
        // same for one to one
        // correspondence
        if (n != m)
            return false;
 
        // For counting the previous appearances
        // of character in both the strings
        let countChars1 = new Array(CHAR);
        countChars1.fill(0);
        let countChars2 = new Array(CHAR);
        countChars2.fill(0);
 
        // Process all characters one by one
        for(let i = 0; i < n; i++)
        {
            countChars1[str1[i].charCodeAt()-'a']++;
            countChars2[str2[i].charCodeAt()-'a']++;
        }
            // For string to be isomorphic the
            // previous counts of appearances of
            // current character in both string
            // must be same if it is not same we
            // return false.
           for(let i = 0; i < n; i++) {
            if (countChars1[str1[i].charCodeAt()-'a'] !=
                countChars2[str2[i].charCodeAt()-'a'])
            {
                return false;
            }
        }
        return true;
    }
     
    document.write(isoMorphic("aab", "xxy") ? 1 + "</br>" : 0 + "</br>");
    document.write(isoMorphic("aab", "xyz") ? 1 : 0);
 
</script>

C#

// C# program to check if two strings
// areIsIsomorphic
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    static bool areIsomorphic(char[] str1, char[] str2)
    {
 
        Dictionary<char, char> charCount
            = new Dictionary<char, char>();
        char c = 'a';
        for (int i = 0; i < str1.Length; i++) {
            if (charCount.ContainsKey(str1[i])
                && charCount.TryGetValue(str1[i], out c)) {
                if (c != str2[i])
                    return false;
            }
            else if (!charCount.ContainsValue(str2[i])) {
                charCount.Add(str1[i], str2[i]);
            }
            else {
                return false;
            }
        }
        return true;
    }
 
    /* Driver code*/
    public static void Main()
    {
 
        string str1 = "aac";
        string str2 = "xxy";
 
        // Function Call
        if (str1.Length == str2.Length
            && areIsomorphic(str1.ToCharArray(),
                             str2.ToCharArray()))
            Console.WriteLine(1);
        else
            Console.WriteLine(0);
 
        Console.ReadLine();
    }
}

Java

// Java program to check if two strings
// areIsIsomorphic
import java.util.*;
 
public class GFG {
 
  static boolean areIsomorphic(char[] str1, char[] str2)
  {
 
    HashMap<Character, Character> charCount
      = new HashMap();
    char c = 'a';
    for (int i = 0; i < str1.length; i++) {
      if (charCount.containsKey(str1[i])) {
        c = charCount.get(str1[i]);
        if (c != str2[i])
          return false;
      }
      else if (!charCount.containsValue(str2[i])) {
        charCount.put(str1[i], str2[i]);
      }
      else {
        return false;
      }
    }
    return true;
  }
 
  /* Driver code*/
  public static void main(String[] args)
  {
 
    String str1 = "aac";
    String str2 = "xxy";
 
    // Function Call
    if (str1.length() == str2.length()
        && areIsomorphic(str1.toCharArray(),
                         str2.toCharArray()))
      System.out.println(1);
    else
      System.out.println(0);
  }
}
 
// This code is contributed by phasing17

Python3

# Python3 program to check if two strings are IsIsomorphic
 
#this function returns true if str1
#and str2 are isomorphic
def areIsomorphic(str1, str2):
    #initializing a dictionary
    #to store letters from str1 and str2
    #as key value pairs
    charCount = dict()
    #initially setting c to "a"
    c = "a"
    #iterating over str1 and str2
    for i in range(len(str1)):
        #if str1[i] is a key in charCount
        if str1[i] in charCount:
            c = charCount[str1[i]]
            if c != str2[i]:
                return False
        #if str2[i] is not a value in charCount
        elif str2[i] not in charCount.values():
            charCount[str1[i]] = str2[i]
        else:
            return False
    return True
         
#Driver Code
str1 = "aac"
str2 = "xxy"
 
#Function Call
if (len(str1) == len(str2) and areIsomorphic(str1, str2)):
    print(1)
else:
    print(0)
 
 
#this code is contributed by phasing17

Javascript

<script>
// JavaScript program to check if two strings are IsIsomorphic
 
// this function returns true if str1
// and str2 are isomorphic
function areIsomorphic(str1, str2)
{
    // initializing an object
    // to store letters from str1 and str2
    // as key value pairs
    var charCount = {};
     
    // initially setting c to "a"
    var c = "a";
     
    // iterating over str1 and str2
    for (var i = 0; i < str1.length; i++)
    {
     
        // if str1[i] is a key in charCount
        if (charCount.hasOwnProperty(str1[i]))
        {
            c = charCount[str1[i]];
            if (c != str2[i])
                return false;
        }
         
        // if str2[i] is not a value in charCount
        else if (!Object.values(charCount).includes(str2[i]))
        {
            charCount[str1[i]] = str2[i];
        }
        else
            return false;
    }
    return true;
}
            
// Driver Code
var str1 = "aac";
var str2 = "xxy";
 
// Function Call
if (str1.length == str2.length && areIsomorphic(str1, str2))
    document.write(1);
else
    document.write(0);
 
// This code is contributed by phasing17.
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *