Solution: Isomorphic Strings

Let's solve the Isomorphic Strings problem using the Hash Map pattern.

We'll cover the following

Statement#

Given two strings, check whether two strings are isomorphic to each other or not.  Two strings are isomorphic if a fixed mapping exists from the characters of one string to the characters of the other string. For example, if there are two instances of the character "a"  in the first string, both these instances should be converted to another character (which could also remain the same character if "a" is mapped to itself) in the second string. This converted character should remain the same in both positions of the second string since there is a fixed mapping from the character "a" in the first string to the converted character in the second string.

Note: Two different characters cannot map to the same character. Furthermore, all the instances of a character must be replaced with another character while protecting the order of characters.

Constraints:

  • Both the strings consist of valid ASCII characters.

  • The length of the string is 00 ≤\leq length ≤\leq 5×1045 \times 10^{4}.

  • The length of both strings is the same.

Solution#

We can use the concept of hash maps to solve the problem more efficiently. The idea is to use a suitable data structure (dictionary) to store the mapping of characters of string1 to characters of string2 and vice versa.

We use the following two hash maps:

  • map_str1_str2: This stores the mapping from string1 to string2.

  • map_str2_str1: This stores the mapping of the characters from string2 to string 1.

Since the length of both strings is the same, we can traverse the indexes of either one of the two strings in a loop.

Within the loop, we do the following:

Note: i represents the ithi^{th} iteration of the loop which traverses the string.

  • We check if string1[i] is present as a key in map_str1_str2 and that the value corresponding to this key is not string2[i]. If both these conditions are satisfied, we return FALSE since a fixed mapping does not exist for string1[i] to string2[i]. Otherwise, we skip this condition and move forward.

  • We check if string2[i] is present as a key in map_str2_str1 and that the value corresponding to this key is not string1[i]. If both these conditions are satisfied, we return FALSE since a fixed mapping does not exist for string2[i] to string1[i]. Otherwise, we skip this condition and move forward.

  • If both the above conditions do not return FALSE, it means the mapping is not defined in either hash map. So we add the key-value pairs of the mapping from the string1[i] to string2[i] and vice versa in the respective hash maps.

  • If the loop ends successfully, it means both the strings are isomorphic since no condition that invalidates the isomorphic properties of both strings was met in the loop.

The slides below illustrate how we’d like the algorithm to run:

Created with Fabric.js 3.6.6 We'll traverse the strings and store the mapping in their respective hash maps to verify whether or not these strings are isomorphic. string1 a l l string2 e g g

1 of 5

Created with Fabric.js 3.6.6 Mapping from string1 to string2 Mapping from string2 to string1 string1 a l l string2 e g g char1 a char2 e No current mapping exists of these characters, so the characters aremapped accordingly in their respective hash maps. a : e e : a

2 of 5

Created with Fabric.js 3.6.6 string1 a l l string2 e g g char1 l char2 g Mapping from string1 to string2 Mapping from string2 to string1 No current mapping exists of these characters, so the characters aremapped accordingly in their respective hash maps. a : e l : g e : a g : l

3 of 5

Created with Fabric.js 3.6.6 char1 l char2 g l => g string1 a l l string2 e g g Mapping from string1 to string2 g => l Mapping from string2 to string1 The mapping of both the characters already exists in the hash maps. char1is mapped to char2 and vice versa in hash maps, so this is a valid mapping. a : e l : g e : a g : l

4 of 5

Created with Fabric.js 3.6.6 l => g string1 a l l string2 e g g Mapping from string1 to string2 Mapping from string2 to string1 g => l a : e l : g e : a g : l We've traversed the entire string, without encountering any conditionthat invalidates the isomorphic properties of both the strings. Therefore, the algorithm returns TRUE.

5 of 5

We can see the code of this solution below:

Isomorphic Strings

Time complexity#

The time complexity for the solution is going to be O(n)O(n), where nn is the length of the string.

Space complexity#

The space complexity for this solution will beO(1)O(1) as the set of ASCII characters are fixed and in the dictionary we store valid ASCII characters.

Isomorphic Strings

Logger Rate Limiter