Isomorphic Strings

easy string hash map

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.

Inputs = "egg", t = "add"

Outputtrue

e↔a and g↔d are consistent throughout.

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    s_to_t, t_to_s = {}, {}
    for a, b in zip(s, t):
        if a in s_to_t and s_to_t[a] != b:
            return False
        if b in t_to_s and t_to_s[b] != a:
            return False
        s_to_t[a] = b
        t_to_s[b] = a
    return True

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;
  const sToT = new Map(), tToS = new Map();
  for (let i = 0; i < s.length; i++) {
    const a = s[i], b = t[i];
    if (sToT.has(a) && sToT.get(a) !== b) return false;
    if (tToS.has(b) && tToS.get(b) !== a) return false;
    sToT.set(a, b);
    tToS.set(b, a);
  }
  return true;
}

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

bool isIsomorphic(string s, string t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, char> sToT, tToS;
    for (size_t i = 0; i < s.size(); ++i) {
        char a = s[i], b = t[i];
        if (sToT.count(a) && sToT[a] != b) return false;
        if (tToS.count(b) && tToS[b] != a) return false;
        sToT[a] = b;
        tToS[b] = a;
    }
    return true;
}

Explanation

Two strings are isomorphic when there is a consistent one-to-one mapping between their characters. "One-to-one" matters in both directions, so we keep two hash maps: s_to_t and t_to_s.

We walk both strings together. For each pair (a, b), we check that a has not already been mapped to a different letter, and that b has not already been claimed by a different letter. If either check fails, the mapping is inconsistent and we return false.

The second map is what prevents two distinct characters from collapsing onto the same target. Without it, "badc" and "baba" would wrongly pass.

Example: s = "egg", t = "add". We record e→a and a→e, then g→d and d→g; the second g/d pair agrees with what we stored, so the answer is true.

If we reach the end with no conflicts, every character lined up consistently and we return true.

Time: O(n) Space: O(σ)