String isomorphism

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we will learn about string isomorphism and algorithms to solve this problem efficiently.

Example 2: Consider strings "PINK" and "LOOT".
The strings are not isomorphic because there are 4 unique characters in the first string "PINK" but there are only 3 unique characters in the string "LOOT", hence a one to one mapping from characters of the first string to characters of the second string is not possible.

Implementation

Problem- Given two strings S1 and S2, the program must return "true" or 1 as the output if the strings are isomorphic else it should return "false" or 0 as the output.

We can implement the string isomorphism problem in the following two ways:

Naive solution
Solution using hashing

Naive solution

In the naive approach, we need to check if every character of the first string maps to the same character in the second string, along with this, we also need to check that no two characters of the first string map to the same character in the second string.

#function to check for string isomorphism, input two strings S1 and S2
def strIsomorphism(S1, S2):
    
    #if lengths of the strings are not equal then they cannot be isomorphic
    if len(S1) != len(S2):
        return 0
    
    #mapTable is a dictionary to store the mappings 
    mapTable = {}
    
    
    #iterating over all the characters of the first string
    for i in range(len(S1)):
        c1 = S1[i]
        c2 = S2[i]
        

        if c1 in mapTable:
            if mapTable[c1] != c2:
                return 0;
        else:
            mapTable[c1] = c2
 
            
    for i in range(len(S2)):
        c1 = S1[i]
        c2 = S2[i]
        
        if c2 in mapTable:
            if mapTable[c2] != c1:
                return 0
    return 1

if __name__ == '__main__':
    S1 = 'WXYZABCXYZ'
    S2 = 'PQRSTUVQRS'
    S3 = 'YWSUIOD'
    S4 = 'QRUSJHS'
    result1 = strIsomorphism(S1, S2)
    result2 = strIsomorphism(S3, S4)
    
    if result1 == 1:
        print(f'{S1} and {S2} are isomorphic.')
    else:
        print(f'{S1} and {S2} are not isomorphic.');
        
        
    if result2 == 1:
        print(f'{S3} and {S4} are isomorphic.')
    else:
        print(f'{S3} and {S4} are not isomorphic.');

Output
WXYZABCXYZ and PQRSTUVQRS are isomorphic.
YWSUIOD and QRUSJHS are not isomorphic.

Time complexity

First we need to check if the every character of the first string is mapped to the same character in the second string, then we will have to check if every character of the second string is mapped to the same character in the first string.
Hence the time complexity would be O(n^2).

Solution using Hashing

We use a new hashmap named mapTable to store the mappings of the characters of the first string S1 and the second string S2.
We also use a set named List to store the already mapped characters.
Now we iterate over the characters of the first string one by one
If the character in string S1 is not in the mapTable, find if the corresponding string S2 character is in the List, if its in the list then the strings are not isomorphic, if not then add the character mapping in the mapTable and add the character from S2 to List.
If the character in string S1 is in the mapTable, then get the mapping from the mapTable, now compare the mapped character and the character read from string S2, if both the characters are same then go to step 3, else the strings are not isomorphic.
The strings are isomorphic if the string S1 is completely iterated.

Working

Example- 1

Consider the strings S1 ='WXAW' S2 = 'PQSP'
Initially the hashmap mapTable and the set List will be empty.
Now iterate over the first string S1, c1 = 'W', c2 = 'P', since 'W' is not in the mapTable, we check if the corresponding character 'P' is in the List, since its not there, we add the mapping to the mapTable, and 'P' to List.

mapTable
W -> P

List
P
Now the next character will be c1 = 'X', c2 = 'Q' since 'X' is not in the mapTable, we check if the corresponding character 'Q' is in the List, since its not there, we add the mapping to the mapTable, and 'Q' to List.

mapTable
W -> P
X -> Q

List
P
Q
Now the next character will be c1 = 'A', c2 = 'S', since 'A' is not in the mapTable, we check if the corresponding character 'S' is in the List, since its not there, we add the mapping to the mapTable, and 'S' to List.

mapTable
W -> P
X -> Q
A -> S

List
P
Q
S
Now the next character will be c1 = 'W', c2 = 'P', since it's already in the mapTable, the mapped character from mapping is 'P' and c2 = 'P' are same, so the character is mapped correctly and its the last character in the first string, so the strings S1 and S2 are isomorphic.

Example- 2

Consider the strings S1 ='REES' S2 = 'PQSO'
Initially the hashmap mapTable and the set List will be empty.
Now iterate over the first string S1, c1 = 'R', c2 = 'P', since 'R' is not in the mapTable, we check if the corresponding character 'P' is in the List, since its not there, we add the mapping to the mapTable, and 'P' to List.

mapTable
R -> P

List
P
Now the next character in the first string S1, c1 = 'E', c2 = 'Q', since 'E' is not in the mapTable, we check if the corresponding character 'Q' is in the List, since its not there, we add the mapping to the mapTable, and 'Q' to List.

mapTable
R -> P
E -> Q

List
P
Q
Now the next character in the first string S1, c1 = 'E', c2 = 'S', since 'E' is already in the mapTable, the mapped character in the mapping is 'Q' but c2 = 'S', since they're not the same, the strings are not isomorphic.

Implementation


#function to check for string isomorphism, input two strings S1 and S2
def strIsomorphism(S1, S2):
    
    #if lengths of the strings are not equal then they cannot be isomorphic
    if len(S1) != len(S2):
        return 0
    
    #mapTable is a dictionary to store the mappings 
    mapTable = {}
    
    #List is a set used to store characters of the second string that are already mapped
    List = set()
    
    #iterating over all the characters of the first string
    for i in range(len(S1)):
        c1 = S1[i]
        c2 = S2[i]
        
        #checking if c1 is already mapped
        if c1 in mapTable:
            #if c1 is already mapped and the mapped character doesn't match c2 then the strings are not isomorphic
            if mapTable[c1] != c2:
                return 0;
        else:
            #if c2 is already mapped then its not a unique mapping and hence strings can't be isomorphic
            if c2 in List:
                return 0
                
            #add the mapping to the mapTable and the charactere of the second string to the set List    
            mapTable[c1] = c2
            List.add(c2)
            
    return 1

if __name__ == '__main__':
    S1 = 'WXYZABCXYZ'
    S2 = 'PQRSTUVQRS'
    S3 = 'YWSUIOD'
    S4 = 'QRUSJHS'
    result1 = strIsomorphism(S1, S2)
    result2 = strIsomorphism(S3, S4)
    
    if result1 == 1:
        print(f'{S1} and {S2} are isomorphic.')
    else:
        print(f'{S1} and {S2} are not isomorphic.');
        
        
    if result2 == 1:
        print(f'{S3} and {S4} are isomorphic.')
    else:
        print(f'{S3} and {S4} are not isomorphic.');

Output
WXYZABCXYZ and PQRSTUVQRS are isomorphic.
YWSUIOD and QRUSJHS are not isomorphic.

Time complexity

In this approach, we store the mappings of the characters as we iterate over them leading to an efficient solution. Since this approach uses hashing to check if the strings are isomorphic, and hence looping only once, the time complexity is linear or O(n).

Table of contents:

Implementation

Naive solution

Time complexity

Solution using Hashing

Implementation

Time complexity