Isomorphic Strings

Intuition

• We want one to one AND onto.
• Therefore, we need two hash maps, one which checks if 2 x’s map to a y, and another which checks if 2 y’s map to an x.
• If in each case you are one to one and onto, then return True else False.
• Isomorphic in this scenario means replacing characters such that they are the same size and one to one and onto.

Complexity

Runtime

$O(N)$

Space

$O(N)$ to store the two hashmaps of size N

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
 
        hmt = {}
        hms = {}
        for i in range(len(s)):
            if t[i] in hmt:
                # No two characters may map to the same character
                if s[i] != hmt[t[i]]:
                    return False
            if s[i] in hms:
                if t[i] != hms[s[i]]:
                    return False
            
            hmt[t[i]] = s[i]
            hms[s[i]] = t[i]
        return True

Notes

---

References

https://leetcode.com/problems/isomorphic-strings/