Isomorphic Strings

Easy· bijection· hash map

Problem

Two strings of equal length are isomorphic if the characters of the first can be consistently replaced to produce the second. Each character must map to exactly one character, and no two different characters may map to the same one. Decide whether the given pair is isomorphic.

Examples

Input: s = "paper", t = "title"

Output: true

p->t, a->i, e->l, r->e is a consistent one-to-one mapping.

Input: s = "foo", t = "bar"

Output: false

o would need to map to both a and r.

Constraints

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• Any valid ASCII characters

Hints & approach

Hint 1

A single map from s to t is not enough; why?

Hint 2

Keep mappings in both directions and check them as you go.

Approachtry the hints first

Walk both strings together, maintaining a map from s-characters to t-characters and another from t-characters to s-characters. For each pair (a, b), if a already maps to something other than b, or b already maps to something other than a, return false; otherwise record both directions. If the scan completes, the mapping is a bijection and the strings are isomorphic.

Time O(n) · Space O(k) for k distinct characters

← PreviousLongest Common Prefix Next →Rotate String