Python Program to check for Isomorphism of Strings

What is the Isomorphism of Strings?

Two strings are isomorphic if the characters in String1 can be replaced to get String2. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. For example,

  • EGG and ADD
  • ACAB and XCXY
Checking for Isomorphism of Strings in Python

Program to check whether the two given Strings are Isomorphic or not

 

The objective is to check if the two given strings, String1 and String2, are Isomorphic to each other or not. In order for two strings such as String1 and String2 to be Isomorphic, Each character of String1 must map to each character of String2 with altering the order of their occurrence.

For instance, In the adjacent figure, We have two examples. Let’s go through them one by one. The first example has String1 and String2 as “ABACBA” and “XPXCPW” respectively. As we can see,  when we map the characters of String1 onto the characters on String2, we notice that the character “A” of String1 is mapping on to more than one character of String2 i.e both “X” and “W”. As the character “A” has more than once reference in String2, The two strings, String1 and String2, are not Isomorphic in nature.

Similarly, In the second example, the strings, String1 and String2, are “ABACBA” and “XPXCPX” respectively. Now when we map the characters of String1 onto String2, we can see that they all map perfectly. The characters “A”, “B” and “C” of String1 map with the characters “X”, “P” and “C” of String2. Therefore, String1 and String2 are Isomorphic in nature.

Checking for Isomorphism of Strings in Python

Python Code

def isisomorphic(str1,str2):
  if len(str1)!=len(str2):
    return False
  else:
    map1,map2={},{}
    for i in range(len(str1)):
      ch1,ch2=str1[i],str2[i]
      if ch1 not in map1:
        map1[ch1]=ch2
      if ch2 not in map2:
        map2[ch2]=ch1
      if map1[ch1]!=ch2 or map2[ch2]!=ch1:
        return False
  return True

print(isisomorphic(input(),input()))

Output

egg
gag
False

Explanation.

The Objective is to check if the characters of the string String1 maps onto the characters of the string String2 correctly. For the two strings, String1 and String2, to be Isomorphic, String1’s characters must map onto the characters of String2 in such a way that the order isn’t altered and each character of String1 must map to on one character of String2.

The algorithm for the above code is as follow:

  1. Define a function isisomorphic() that takes string1 and string2 as parameters. 
  2. Check if the length of str1 is equal to str2 using the len() function. If True proceed, else return False.
  3. initialise two dictionaries map1 and map2.
  4. Using a for loop iterate through str1 and str2.
  5. Check if the character ch1 is not in map1, if true add to map1 as map1[ch1] = ch2.
  6. Check if the character ch2 is not in map2, if true add to map2 as map2[ch2] = ch1.
  7. Now using map1 and map2 dictionaries, map the characters ch1 and ch2 with each other, if they don’t match, return False. Else, return True.
  8. Call the function isisomorphism() inside the print() function. for arguments using input() function.

The output for the above code is True if they’re isomorphic in nature, False otherwise.

For more solutions, click the button.