Isomorphic Strings

Q: Why do you need two hash maps for isomorphic strings?

A map from s to t catches one character of s renamed two ways. It cannot see two characters of s renamed to the same character, as in ab and aa . The map from t back to s catches that case.

Q: Is isomorphism symmetric?

Yes. A one-to-one renaming can be undone, so if s renames into t , reversing every name turns t back into s . isIsomorphic(s, t) and isIsomorphic(t, s) always agree.

EasyHashing

+10

Two strings are isomorphic when you can rename the characters of the first to get the second. Every copy of a character gets the same new name, two different characters never get the same name, and a character may keep its own. For two strings s and t of the same length, return true when they are isomorphic and false when they are not.

Function

isIsomorphic(s: string, t: string) → boolean

sstring: the string to rename, letters and digits
tstring: the string to reach, the same length as s
Returnsboolean: true if a one-to-one renaming of the characters of s gives t

Constraints

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s and t contain only English letters and digits. Upper and lower case are different characters.

Examples

Input: s = "noon"t = "deed"
Output: true
Explanation: Rename n to d and o to e. Every position agrees with that renaming, and the two letters get different names.

Input: s = "moon"t = "deed"
Output: false
Explanation: Left to right, m becomes d and o becomes e, and then n would also have to become d. Two different letters cannot share a name, so the answer is false.

Input: s = "r2d2"t = "c3p3"
Output: true
Explanation: r becomes c, 2 becomes 3 and d becomes p. Digits are characters too, and both 2s become 3.

Follow-up

Given a list of words, can you group together the ones that are isomorphic to each other without comparing every pair of words?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A renaming must work both ways: each character of s turns into one character of t, and each character of t comes from one character of s. Two maps, one per direction, check both in a single pass.

Compare every pair of positions

Correct, but does not finish on the largest tests

Intuition

A renaming keeps equal characters equal and different characters different. So for every pair of positions i and j, s[i] == s[j] must give the same answer as t[i] == t[j]. That is also enough: if every pair agrees, renaming each character of s to the character of t at its positions is well defined and never gives two characters one name. In moon and deed, positions 0 and 3 hold different letters in s but d twice in t, so the answer is false.

There are about n²/2 pairs: 2 × 10^8 comparisons at n = 2 × 10^4 when no pair stops the loop early.

Algorithm

Loop over every index i, and for each one over every later index j.
Work out whether s[i] equals s[j], and whether t[i] equals t[j].
If the two answers differ, return false.
After the last pair, return true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

Two maps, one per direction

Intuition

Build the renaming as you read. Map sToT records what each character of s became, and tToS records where each character of t came from. At position i, with a = s[i] and b = t[i], either both are new and you link them, or they must already point at each other.

One map is not enough. With only sToT, moon and deed pass, because no letter of s is renamed two ways. The fault is that m and n both become d, and at position 3 tToS already says d came from m.

Each position costs a few map operations, so the time is O(n). Every character code is below 128, so each map can be a 128-entry array: O(1) space. The R and Swift versions first copy the strings into code arrays, which takes O(n).

Algorithm

Create two empty maps, sToT and tToS.
For each index i, let a = s[i] and b = t[i].
If a is not in sToT and b is not in tToS, map a to b and b to a.
Otherwise, if sToT[a] is not b or tToS[b] is not a, return false.
After the last index, return true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

Pitfalls and edge cases

Keeping one map from s to t. It accepts moon and deed, and ab and aa.
Comparing how many times each character appears. abcabc and xyzxzy both use three characters twice each, yet the second b sits over z where the first sat over y.
Treating case as equal. aA holds two different characters, so it cannot become bb.
Sizing the array maps for a to z only. Upper case letters and digits fall outside that range; index by the full character code with 128 entries.

Frequently asked questions4

What is the time complexity of Isomorphic Strings?

The two-map solution reads each position once, so it runs in O(n) time. The maps hold at most one entry per possible character, 62 letters and digits, so the extra space is O(1). Comparing every pair of positions takes O(n²).

Why do you need two hash maps for isomorphic strings?

A map from s to t catches one character of s renamed two ways. It cannot see two characters of s renamed to the same character, as in ab and aa. The map from t back to s catches that case.

Is isomorphism symmetric?

Yes. A one-to-one renaming can be undone, so if s renames into t, reversing every name turns t back into s. isIsomorphic(s, t) and isIsomorphic(t, s) always agree.

How else can you check if two strings are isomorphic?

Replace every character by the position where it first appears and compare the results. noon and deed both become 0 1 1 0, while moon becomes 0 1 1 3. It is also O(n) time, with O(n) memory for the two patterns.

def isIsomorphic(s, t):
    # Write code here

Test #1

Test #2

Test #3

Arguments

s = "noon"
t = "deed"

Expected Output

true