Isomorphic Strings

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