# Isomorphic Strings

Difficulty Level Easy
Hash Hashing StringViews 1881

Isomorphic Strings – Given two strings we need to check if for every occurrence of a character in string1 there is a unique mapping with characters in string2. In short, check, if there is one to one mapping or not.

## Example

Input

str1 = “aab”

str2 = “xxy”

Output

True

Explanation

map ‘x’ with ‘a’ and map ‘y’ with ‘b’.

## Algorithm for Isomorphic Strings

length of string one and two must be the same.

Iterate each character of the string1. When we encounter the character for the first time in string1 then check the current of string2. If the current of string2 is already present in the map  then return false else map current of string1 with string2 and mark current of string 2 as taken. If we did not encounter the character for the first time in string1 then check if the previous appearance mapped to the same character of string2.

## C++ code for Isomorphic Strings

```// 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 ismorphic
bool areIsomorphic(string str1, string str2)
{

int m = str1.length(), n = str2.length();

// Length of both strings must be same for one to one
// corresponance
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 code for Isomorphic Strings

```// 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 ismorphic
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
// corresponance
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);
}
}```
```1
0```

Reference

Translate »