Isomorphic Strings
The key idea
Isomorphism is a one-to-one (bijective) character mapping. As you scan the two strings in lockstep, the pair
(s[i], t[i]) must obey two rules at once: s[i] must always map to the same t[i] it mapped to before (no character maps to two targets), and that t[i] must not already be claimed by a different source character (no two characters collapse into one target). Tracking both directions catches every violation in a single linear pass.Problem
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.
Constraints
1 <= s.length <= 5 * 10^4t.length == s.lengthsandtconsist of any valid ASCII character.
Examples
Input: s = "egg", t = "add"
Output: true
Input: s = "foo", t = "bar"
Output: false
Input: s = "paper", t = "title"
Output: true
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM