Isomorphic Strings

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

Given two strings, return true if each character in one can be replaced by the char in the other. No two chars can map to the same char.
egg -> add ✅ | e maps to a and g maps to d
foo -> bar ❌ | f maps to b, o maps to both a and r

Key Observations

(Patterns, constraints, or hints in the problem statement.)

Mapping is needed therefore use Hash Map

Main Concepts Used

(Mark the CS concepts or algorithms used.)

Time & Space Complexity

Time: $O (n)$ → Reason: Iterating through each char in both input strings
Space: $O (n)$ → Reason: Storing mapping of each char

Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapOfStoT = {} # O(n)
        mappedSoFar = set() # O(1)

        for i in range(len(s)): # O(n + m)
            charInS = s[i]
            charInT = t[i]

            if charInS in mapOfStoT:
                # check whether mapping matches charInT
                storedMapping = mapOfStoT[charInS]
                if storedMapping != charInT:
                    return False
            else:
                if charInT in mappedSoFar:
                    return False
                mapOfStoT[charInS] = charInT
                mappedSoFar.add(charInT)
        return True

Common Mistakes / Things I Got Stuck On

Forgot about the requirement: No two chars can map to the same letter
Easier way to think about this is that bar needs to be isomorphic to foo and also vice versa

Optimized Code

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapStoT, mapTtoS = {}, {}

        for c1, c2 in zip(s, t):
            if c1 in mapStoT:
                if c2 != mapStoT[c1]:
                    return False
            else:
                mapStoT[c1] = c2

            if c2 in mapTtoS:
                if c1 != mapTtoS[c2]:
                    return False
            else:
                mapTtoS[c2] = c1
        return True