Java program to check Isomorphic Strings

Java program to check Isomorphic Strings

Write a Java program to check Isomorphic Strings is one of the common coding interview questions. This question is asked in big companies like LinkedIn also. In such companies they will look for an optimal solution rather than a plain one. In this post we will see a solution in Java.

What are Isomorphic Strings

Two Strings S1 and S2 are said to be Isomorphic, if each character in the String S1 can be replaced with another character to get the String S2. There are some conditions attached to it. They are,

  • The length of both the Strings should be same.
  • The order of the characters should not be changed while replacing it.
  • No two characters may map to the same character.
  • A letter can be replaced with itself.

Examples of Isomorphic Strings

“paper” and  “title” are isomorphic. Here ‘p’ can be mapped to ‘t’, ‘a’ to ‘i’, ‘e’ to ‘l’ and ‘r’ to ‘e’.

Another example would be “app” and “foo”. ‘a’ -> ‘f’ and ‘p’ -> ‘o’.

Both these examples satisfies all the conditions mentioned above.

Now consider the following example,

“bar” and “foo”. These two are not isomorphic since ‘b’ maps to ‘f’ and both ‘a’ and ‘r’ maps to ‘o’. So it fails to satisfy the condition 3.

Java Implementation

Solution#1

In this approach HashMap is used to track character to character mapping. Here is the Java program.

Below is the output of the above program.

Solution#2

This is a modified version of Solution#1. In this program, in addition to HashMap, a HashSet is used to contain the mapped characters and then this HashSet is checked to see if the character in S2 is already mapped to some other character in S1.  This approach takes less time than map.containsValue() to check if the character is already mapped. Below is the program.

Below is the output of the above program.

Hope you find this post on Isomorphic Strings useful.

There can be many ways of solving this problem. If you have any better approach post it in the comments section.

The following two tabs change content below.
Working as a Java developer since 2010. Passionate about programming in Java. I am a part time blogger.

Add Comment

Required fields are marked *. Your email address will not be published.