< Back

205. Isomorphic Strings

This question asks if we can replace the first string with the characters in the second string in the
same order. Initially, you think this would be related to frequency, but it's not. We still use a
hash map to track characters encountered, however, we actually use the map to map to the other
string for our replacement character.

We basically have two checks, if the characters are not mapped to each other, we map them. If one of
the characters are mapped, we know that there's a collisions, therefore the string is not

The solution is as follows:

  from collections import defaultdict

  class Solution:
      def isIsomorphic(self, s: str, t: str) -> bool:
          s_map = defaultdict(str)
          t_map = defaultdict(str)

          for s_char, t_char in zip(s, t):
              if s_char not in s_map and t_char not in t_map:
                  s_map[s_char] = t_char
                  t_map[t_char] = s_char

              elif s_map[s_char] != t_char or t_map[t_char] != s_char:
                  return False

          return True

_ Time Complexity:

  O(n) - We iterate through all characters in both strings.

_ Space Complexity:

  O(1) - We store at most 256 characters of hashes in our dictionary.