Isomorphic Strings
(#205), Easy
Category: Hash Table, String
Problem Statement
Given two strings `s` and `t`, determine if they are isomorphic. Two strings are isomorphic if the characters in `s` can be replaced to get `t` such that: 1. Each character in `s` maps to exactly one character in `t`. 2. No two characters may map to the same character. 3. Character order must be preserved. Return `true` if `s` and `t` are isomorphic; otherwise, return `false`.
Examples
Input: s = "egg", t = "add"
Output: true
Explanation: 'e' → 'a', 'g' → 'd'. Mapping is consistent and unique.
Input: s = "foo", t = "bar"
Output: false
Explanation: 'o' maps to two different characters → invalid.
Input: s = "paper", t = "title"
Output: true
Explanation: 'p'→'t', 'a'→'i', 'e'→'l', 'r'→'e'. Mapping is consistent.
Input: s = "ab", t = "aa"
Output: false
Explanation: Both 'a' and 'b' map to 'a' → violates one-to-one mapping.
Approach
Approach: Two Hash Maps for Bidirectional Mapping
- If `s` and `t` are not of equal length, return false immediately.
- Initialize two hash maps: `mapST` for mapping from `s → t`, and `mapTS` for mapping from `t → s`.
- Iterate through each character of both strings:
- - If a character from `s` is already mapped, check if it matches the current `t` character.
- - Also check if the `t` character is already mapped by another `s` character.
- - If any mismatch is found in either direction, return false.
- If the loop completes without mismatch, return true.
// 🔹 Approach: Two Hash Maps (s → t and t → s)
var isIsomorphic = function(s, t) {
if (s.length !== t.length) return false;
let mapST = new Map();
let mapTS = new Map();
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (
(mapST.has(charS) && mapST.get(charS) !== charT) ||
(mapTS.has(charT) && mapTS.get(charT) !== charS)
) {
return false;
}
mapST.set(charS, charT);
mapTS.set(charT, charS);
}
return true;
};Complexity
Time: O(n) – single traversal over the string length
Space: O(n) – storing mappings in two hash maps