205. Isomorphic Strings

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.

Example 1:

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

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

This problem is purely based on bijection in mathematics .That is one to one mapping is what we are dealing with.

Approach 1:

Using hash set and list

We will iterate through the string and we see a character in ‘s’ that is not yet mapped to any character , we should check if the character in ‘t’ is also not mapped to any character yet , then we add it as a new mapping to the hash set named ‘hash’. Else if there is new character in ‘s’ but its corresponding character in ‘t ‘ is already mapped to a different character then it should not be isomorphic so we return false. In the last else case we check if the character in ‘s’ is not mapped to any different character compared to previous mapping which was added to the hash set.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        hash = dict()
        list_set=set()
        for i in range(len(s)):
            if s[i] not in hash:
                if t[i] not in list_set:
                    hash[s[i]]=t[i]
                    list_set.add(t[i])
                else:
                    return False
            else:
                if(hash[s[i]]!=t[i]):
                    return(False)
        return(True)

Time: O(n)

Space: O(n)