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