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.
Worked 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.
Hints
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.
Solution approach
- 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.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n) time; O(k) for k distinct characters auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗