Isomorphic Strings

Problem

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

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = “egg”, t = “add”

Output: true

Explanation:

The strings s and t can be made identical by:

• Mapping 'e' to 'a'.

• Mapping 'g' to 'd'.

Example 2:

Input: s = “f11”, t = “b23”

Output: false

Explanation:

The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.

Example 3:

Input: s = “paper”, t = “title”

Output: true

Constraints:

• 1 <= s.length <= 5 * 10:sup:`4`

• t.length == s.length

• s and t consist of any valid ascii character.

Pattern

Hash Table, String

Approaches

Hash Map

Explanation

Observe that if two strings are isomorphic, then the first character in s must map to the first character in t. Similarly, for the second character to the last character. If the 2 strings are isomorphic, this is a one-to-one map. We can use a dictionary to store the one-to-one map from s to t. Iterate through the characters in s and t at the same time. If the s character is not in the dictionary, then add it to the dictionary and to the range set. Check injectivity, that the t character is not in the range set. If the character in s is in the dictionary, then check if it maps to the character in t.

Code

def isIsomorphic(s: str, t: str) -> bool:
    """Checks if 2 strings are isomorphic."""
    d = {}
    d_range = set()
    for s_char, t_char in zip(s, t):
        if s_char in d:
            if d[s_char] != t_char:
                return False
        else:
            if t_char in d_range:
                return False
            else:
                d[s_char] = t_char
                d_range.add(t_char)

    return True

Test

>>> from isomorphic_strings__hash_map import isIsomorphic
>>> isIsomorphic('egg', 'add')
True
>>> isIsomorphic('foo', 'bar')
False
>>> isIsomorphic('paper', 'title')
True

Complexity

\(n\) is the length of the shortest string

Measure	Complexity	Notes
Time	\(O(n)\)	single pass through the strings
Auxiliary Space	\(O(n)\)	dictionary and range set store at most \(n\) key-value pairs

isomorphic_strings__hash_map.isIsomorphic(s: str, t: str) → bool

Checks if 2 strings are isomorphic.