Intuition

Map characters letters, and map seen letters.

Approach

We will need to use two use two structures here.

  • One to map the correspoding character
  • One to keep track of seen chracters, this is necessary becase “no two chracter may map to the same character”

If len is diff, just return false.

Loop through the chracters (s -> cs, t -> ct).

  • if cs was mapped before, and map[cs] == ct, move to the next
  • if cs was mapped before, and map[cs] != ct, return False
  • if cs was not mapped before, and seen[ct], return False
  • else map[cs] = ct, and seen[ct] = True

Complexity

  • Time complexity: O(n)

  • Space complexity: O(1), because we can only have so many letters.

Code

    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        
        if len(s) != len(t):
            return False

        mapping = {}
        seen = {}

        m = len(s)
        for i in range(m):
            
            c_s = s[i]
            c_t = t[i]

            if c_s in mapping and c_t == mapping[c_s]:
                continue

            if c_s in mapping and c_t != mapping[c_s]:
                return False
            
            if c_s not in mapping and c_t in seen:
                return False

            mapping[c_s] = c_t
            seen[c_t] = True
        
        return True