Problem Statement in English

You’re given two strings s and t. You need to determine if they are isomorphic.

The strings are isotropic if there exists a one-to-one mapping of characters from s to t and vice versa.

Approach

We use hash maps and build a character mapping. We iterate through the strings and check if the mapping is consistent, and return our findings.

Solution in Python


class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # store the mapping of `s` to `t`
        lStore = {}

        # store the mapping of `t` to `s`
        rStore = {}

        # iterate through the strings
        for i in range(len(s)):
            # if the mapping is already present in `lStore`
            if s[i] in lStore:
                # if the mapping is not the same as the current mapping
                if lStore[s[i]] != t[i]:
                    # return `False`
                    return False
            # if it is not present
            else:
                # store the mapping
                lStore[s[i]] = t[i]

            # if the mapping is already present in `rStore`
            if t[i] in rStore:
                # if the mapping is not the same as the current mapping
                if rStore[t[i]] != s[i]:
                    # return `False`
                    return False
            # if it is not present
            else:
                # store the mapping
                rStore[t[i]] = s[i]
                
        # if we've reached here, it means the strings are isomorphic
        return True

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ characters at most.

  • Space: $O(n)$
    Since we store the mappings in two dictionaries.

And we are done.