Isomorphic Strings
Problem
Given two strings s and t, determine if they are isomorphic such that the characters in s can be replaced to get t, with a one-to-one mapping between characters and no two characters mapping to the same character.
- 1 ≤ s.length ≤ 5 * 10⁴
- t.length == s.length
- s and t consist of any valid ASCII characters.
Example
s = "egg", t = "add"trueThe character 'e' in s maps to 'a' in t, and 'g' maps to 'd'. The mapping is consistent and one-to-one, so the strings are isomorphic. Consider the strings s = "foo" and t = "bar". The first 'f' maps to 'b', but the second 'o' would need to map to both 'a' and 'r', which is impossible. Thus, they are not isomorphic. The critical insight is that each character in s must map to exactly one character in t, and no two characters in s can map to the same character in t.
Approach
Straightforward Solution
A brute-force approach might try all possible mappings between characters of s and t, which is exponential and infeasible for large strings.
Core Observation
Isomorphism requires a bijection between characters of s and t: each character in s maps to exactly one character in t, and no two characters in s map to the same character in t.
Path to Optimal
The key recognition signals are 'one-to-one mapping' and 'character replacement' which indicate the use of Hash Maps to track mappings from s to t and a set to track used characters in t. This allows checking the mapping consistency in a single pass over the strings.
Optimal Approach
PreviewIterate through both strings simultaneously, maintaining a hash map from characters in s to characters in t and a set of characters already mapped in t. For each character pair, if the character in s is not mapped, check if the character in t is already used; if so, return false…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm iterates through the strings once, performing O(1) average-time hash map and set operations per character.
Space
O(n)
In the worst case, the hash map and set store mappings for all characters in s and t, which is proportional to the length of the strings.
Pattern Spotlight
Hash Maps (One-to-One Mapping Validation)
When verifying a one-to-one mapping between two sequences, maintain a forward mapping and a set of used targets to ensure uniqueness and consistency in a single pass.
Solution
| 1 | class Solution: |
| 2 | def isIsomorphic(self, s: str, t: str) -> bool: |
| 3 | |
| 4 | mapping = {} |
| 5 | used = set() |
| 6 | |
| 7 | for i in range(len(s)): |
| 8 | |
| 9 | c1 = s[i] |
| 10 | c2 = t[i] |
| 11 | |
| 12 | if c1 not in mapping: |
| 13 | if c2 in used: |
| 14 | return False |
| 15 | |
| 16 | mapping[c1] = c2 |
| 17 | used.add(c2) |
| 18 | |
| 19 | else: |
| 20 | if mapping[c1] != c2: |
| 21 | return False |
| 22 | |
| 23 | return True |
Step-by-Step Solution
Track Character Mappings and Used Targets to Validate Isomorphism
| 4 | mapping = {} |
| 5 | used = set() |
Objective
To maintain a mapping from characters in s to characters in t and track which characters in t have been used to ensure a one-to-one mapping.
Key Insight
By storing the mapping from s to t in a hash map and tracking used characters in t with a set, the algorithm can efficiently verify both the consistency of mappings and the uniqueness constraint in a single pass. This avoids the need for nested loops or backtracking and guarantees O(n) time complexity.
Interview Quick-Check
Core Logic
Maintain a hash map for s->t mappings and a set for used characters in t to enforce one-to-one mapping constraints.
State & Boundaries
Check mapping existence before adding new mappings and verify consistency for existing mappings.
Common Pitfalls & Bugs
Failing to check if a character in t is already used by another character in s can lead to incorrect acceptance of non-isomorphic strings.
Iterate Through Characters to Build and Validate Mappings
To iterate through each character pair in s and t, updating the mapping and used set or returning false if a conflict is detected.
Return True After Successful Validation of All Mappings
To confirm that all character mappings are consistent and unique, returning true to indicate isomorphism.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if c2 in used:Check if the current character in t is already used by another character in s.
This check enforces the uniqueness constraint of the mapping, preventing two characters in s from mapping to the same character in t.
return FalseReturn false if the character in t is already used, violating uniqueness.
Immediate termination upon detecting a mapping conflict prevents incorrect acceptance of non-isomorphic strings and saves computation.
if mapping[c1] != c2:Check if the existing mapping for the current character in s matches the current character in t.
Verifying mapping consistency ensures that the established bijection is not violated by conflicting character pairs.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why is it necessary to check both that a character in s maps consistently to a character in t and that no two characters in s map to the same character in t?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Isomorphic Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Isomorphic Strings drill