Checking if two strings are isomorphic →
Today, let us see how we can figure out if two given input strings are isomorphic using a time-efficient algorithm.
Given two strings s1 and s2 if there is a unique mapping from each of the characters of one to the other, then they are isomorphic
For example, anna
and naan
are isomorphic with the mapping a -> n
and n -> a
. Similarly aab
and xxy
are isomorphic with the mapping a -> x
and b -> y
, while aab
and xyz
are not isomorphic. However, anna
and naa
are not isomorphic as there is no direct mapping for the last a
of anna
(a hint that the strings should be of equal length for them to be isomorphic).
An approach is to traverse one of the strings and mark the occurence of the character in the string. The nice thing about character strings is that there are only 256 ASCII characters and hence we can have a character array of size 256 to mark the occurence of characters in a string. Along with marking the occurence, we need to store the mapping of this character to the corresponding (array index) character of the second string.
- During the very first encounter of a character, say the first
a
(index 0) inanna
, we check if the corresponding index in the other stringnaan
has already been visited. - We visit it (i.e. remember it in some algorithmic way).
- We store the mapping of this visit (i.e.
a -> n
). - If we encounter a character again, say the last
a
inanna
, we check for the mapping to see if the corresponding index in the second string is as per our expectations (i.e. obeys the mapping).
The way we maintain the mapping is through an array map
and we also maintain whether we already visited a particular character using an array visited
. Since we need two additional arrays of size 256 each, there is some cost we pay for this space. However, we traverse the input array only once and so it would be O(n) time algorithm. These four steps are noted in the code fragment below for easier reference.