IsomorphicStrings

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.

Solution

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.

Pattern

Hash Table, String

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 IsomorphicStrings import isIsomorphic
>>> isIsomorphic('egg', 'add')
True
>>> isIsomorphic('foo', 'bar')
False
>>> isIsomorphic('paper', 'title')
True

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

Checks if 2 strings are isomorphic.