Isomorphic String : April POTD

Day 8/75:

Question: Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Input: s = "egg", t = "add"
Output: true        

IMP Condition: chars are one to one mapped and are bidirectional.

Intuition:

Our intuition for solving this problem involves iterating through each character of both strings simultaneously and maintaining a mapping between characters of the two strings. We can use two hash maps to store mappings in both directions: from characters in string s to characters in string t, and from characters in string t to characters in string s. By ensuring that each character in one string maps to exactly one character in the other string, we can determine if the strings are isomorphic.

Approach:

We can implement our approach using two hash maps:

1) map1 to store mappings from characters in string s to characters in string t.

2) map2 to track whether characters in string t have already been mapped.

We iterate through each character of both strings simultaneously and update our hash maps accordingly.

If we encounter a character that has already been mapped differently, or if a character in string t has multiple mappings, we return false.

Otherwise, if all characters can be mapped successfully, we return true.

Code:

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the input strings s and t.
• Space Complexity: O(n), as we use two hash maps to store mappings between characters.

Conclusion:

The implemented solution effectively determines whether two given strings are isomorphic by maintaining mappings between characters and ensuring that each character in one string maps to exactly one character in the other string. This approach achieves linear time complexity, making it suitable for processing large input sizes efficiently.