Java - Check if two given strings are isomorphic to each other

Isomorphic Strings

Two strings X and Y are isomorphic strings if all occurrences of each character in X can be replaced with another unique character to get Y and vice-versa.

Example:

String "aab" and "xxy" are isomorphic strings as we can replace 'a' with 'x' and 'b' with 'y' in the first string and get the second string.

Criteria that need to be met for two strings to be isomorphic,

• Both strings must be of same length

• Every occurrence of a character in the first string must be replaced with another character in the second string.

• No two characters (of the first string) may map to the same character (in the second string), but a character may map to itself.

Let's explore given two strings how we can check if the strings are isomorphic.

Naive Solution

The naive approach to this problem would be to consider every character of ‘str1’ and check if all occurrences of it map to same character in ‘str2’.

Algorithm would be defined as below,

1. Check if every character in 'str1' is mapped to the same character in 'str2' for all its occurrences.

2. Even after the above step, two characters in the 'str1' can be mapped to same character in 'str2'.

3. To avoid this, repeat the step 1 for 'str2', Check if every character in 'str2' is mapped to the same character in 'str1' for all its occurrences.

Time complexity of this solution is O(n*n).

It can be improved to a liner complexity of O(n).

Efficient Solution

The efficient solution will take O(n) time to complete.

The idea behind finding the efficient solution is, to store the mappings of processed characters.

Algorithm would be defined as below,

1. If, 'str1' and 'str2' are not same in length, return false.

2. Else,

• If, this character is seen first time in 'str1', then current of 'str2' must have not appeared before. i) If current character of 'str2' is seen, return false. ii) Mark current character of 'str2' as visited. iii) Store mapping of current characters.
  

• Else, check if previous occurrence of str1[i] mapped to same character.

There are multiple ways we can implement this algorithm using different data structures.

In this post i will cover two approaches,

• Using Arrays

• Using Hashing

Array-based approach to check Isomorphic Strings

Please find the complete java code below,

Idea behind this approach is to maintain an integer array and a boolean array,

• Integer array (mappedArray) to store the mappings between characters of 'str1' and their replaced values in 'str2'.

• Boolean array (markedArray) to mark the characters of 'str2' which are already replaced.

Integer Array to store the mappings between characters of 'str1' and 'str2'

This array will be used to store the mapped character's ASCII value from 'str2' in the index position computed by the character's ASCII value from 'str1'.

mappedArray[str1.charAt(i)] = str2.charAt(i);

To maintain the correspondence we are using the ASCII value of the character from 'str1' as the index and ASCII value of the character from 'str2' as the value.

ASCII based approach can be avoided if we use a hash map (instead of array) to maintain the correspondence mappings.

Since the we are storing the ASCII values of the characters, the total number of elements in the mappedArray is 256. In total there are 256 ASCII characters.

Boolean Array to mark the characters of 'str2' which are already replaced

As explained earlier, same character from 'str2' cannot be used to replace more than one character in 'str1'. To achieve this, we track the characters of 'str2' whether they are used for replacement Or not.

We store the boolean value true/false in the index denoting the ASCII value of the character checked on 'str2'.

Let's now have a quick look at the logic in place here.

for(int i=0; i < lenStr1; i++){
    if(mappedArray[str1.charAt(i)] == -1){
        if(markedArray[str2.charAt(i)] == true) return false;
        markedArray[str2.charAt(i)] = true;
        mappedArray[str1.charAt(i)] = str2.charAt(i);
    }
    else if(mappedArray[str1.charAt(i)] != str2.charAt(i)) return false;
}

Here we are looping only once through both strings which results in O(n) time complexity.

Hash-based approach to check Isomorphic Strings

This approach is fairly easy compared to the previous approach.

In this approach we will be implementing the same logic as previous approach with a different data structures like hash map and a set,

• Hash map to store the mapping from characters of 'str1' to 'str2'.

• Set to store the already mapped characters.

Please find the complete java code below,

Here also we are looping only once and simultaneously checking both strings which results in O(n) time complexity.

So, to wrap up, the efficient solution for the Isomorphic String identification problem is of O(n) time complex.

Thank you for Reading!

Cheers!!!