Are Two Strings Isomorphic

easy string hash map

Problem

Strings s and t are isomorphic if there is a bijection between their characters that turns one into the other while preserving order — every occurrence of a letter in s maps to the same letter in t and vice versa. Walk both strings in lockstep with two maps: s→t and t→s. Each new pair must be consistent with anything already recorded in either direction.

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;
}

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