Problem statement

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

Solution

Go symbol by symbol and add direct and inverse connections to hash tables d1 and d2.

  1. If i not in d1 and j in d2, it means, that something is wrong, we have case a -> x, b -> x, return False.
  2. If i not in d1 and j not in d2, it means that we see this pair first time, update both dictionaries.
  3. If i in d1 and d1[i] != j, it means, that we have a -> x, a -> y, return False.
  4. In the end return True if we did not return anyghing before.

Complexity

Time complexity is O(n), space complexity is O(m), where m is size of alphabet to keep dictionaries.

Code

class Solution:
    def isIsomorphic(self, s, t):
        d1, d2 = {}, {}
        for i, j in zip(s,t):
            if i not in d1:
                if j in d2: return False
                else:
                    d1[i] = j
                    d2[j] = i
            elif d1[i] != j: return False
            
        return True