161. Isomorphic Strings

Walk both strings together, building a consistent letter-to-letter mapping in each direction. If a character ever needs to map to two different things — or two characters collide onto the same target — they aren't isomorphic.

Idea

Isomorphism requires a bijection: each character of s maps to exactly one character of t, and vice-versa. Keep two maps (s→t and t→s) and verify consistency as you scan. Two maps are needed to reject cases like "ab" → "aa", where s→t alone would look fine but two different s characters collapse onto one t character.

Algorithm

1. If lengths differ, return false.
2. For each pair (a, b) from zip(s, t):
   • If a is already mapped and map_st[a] != b, return false.
   • If b is already mapped and map_ts[b] != a, return false.
   • Record map_st[a] = b and map_ts[b] = a.
3. Return true.

Worked example: s = "egg", t = "add"

• e→a, a→e. g→d, d→g. Second g→d consistent. → true.

Contrast "badc" → "baba": d→b but b is already mapped from a side... the reverse map catches the collision → false.

Complexity

• Time: O(n).
• Space: O(1) — bounded alphabet.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Character> mapST = new HashMap<>();
        Map<Character, Character> mapTS = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            if (mapST.containsKey(a) && mapST.get(a) != b) {
                return false;
            }
            if (mapTS.containsKey(b) && mapTS.get(b) != a) {
                return false;
            }
            mapST.put(a, b);
            mapTS.put(b, a);
        }
        return true;
    }
}