#205
Isomorphic Strings
Easy Two-way mapping
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether characters of s can be replaced one-to-one to get t (no two characters may map to the same character).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can letters of s be renamed one-to-one to get t?
Why this works: check the mapping in both directions; "ab" → "aa" fails because two letters would map to the same one.
Example: "egg" → "add"
e→a, g→d, g→d ✓ and back a→e, d→g ✓ → true✦Hints open one at a time
A mapping s→t alone isn't enough: "ab" → "aa" would pass.
Track the mapping in both directions.
↗Approach
Keep two arrays: s-char → t-char and t-char → s-char. For each position, if either existing mapping disagrees, return false; otherwise record both.
</>Solution (Java)
class Solution {
public boolean isIsomorphic(String s, String t) {
int[] st = new int[256], ts = new int[256]; // 0 = not mapped yet
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i), b = t.charAt(i);
if (st[a] == 0 && ts[b] == 0) {
st[a] = b;
ts[b] = a;
} else if (st[a] != b || ts[b] != a) {
return false;
}
}
return true;
}
}!Common mistake
Checking only one direction.
Complexity
- Time: O(n).
- Space: O(charset).
Topic: Strings
🎬 Episodes 16–20: video coming soon