Code Implementation

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        map_s_t = {}
        map_t_s = {}
        for c1, c2 in zip(s, t):
            if c1 in map_s_t:
                if map_s_t[c1] != c2:
                    return False
            else:
                map_s_t[c1] = c2
            if c2 in map_t_s:
                if map_t_s[c2] != c1:
                    return False
            else:
                map_t_s[c2] = c1
        return True
      

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) return false;
        unordered_map<char, char> map_s_t, map_t_s;
        for (int i = 0; i < s.length(); ++i) {
            char c1 = s[i], c2 = t[i];
            if (map_s_t.count(c1)) {
                if (map_s_t[c1] != c2) return false;
            } else {
                map_s_t[c1] = c2;
            }
            if (map_t_s.count(c2)) {
                if (map_t_s[c2] != c1) return false;
            } else {
                map_t_s[c2] = c1;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> mapS = new HashMap<>();
        Map<Character, Character> mapT = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (mapS.containsKey(c1)) {
                if (mapS.get(c1) != c2) return false;
            } else {
                mapS.put(c1, c2);
            }
            if (mapT.containsKey(c2)) {
                if (mapT.get(c2) != c1) return false;
            } else {
                mapT.put(c2, c1);
            }
        }
        return true;
    }
}
      

var isIsomorphic = function(s, t) {
    if (s.length !== t.length) return false;
    let mapS = {}, mapT = {};
    for (let i = 0; i < s.length; i++) {
        let c1 = s[i], c2 = t[i];
        if (mapS[c1] !== undefined) {
            if (mapS[c1] !== c2) return false;
        } else {
            mapS[c1] = c2;
        }
        if (mapT[c2] !== undefined) {
            if (mapT[c2] !== c1) return false;
        } else {
            mapT[c2] = c1;
        }
    }
    return true;
};
      

Problem Description

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, with the following constraints:

• Each character in s must be mapped to a character in t in a one-to-one way (no two characters in s map to the same character in t).
• The mapping must be consistent: every occurrence of a character in s must map to the same character in t.
• Characters may map to themselves.
• Both strings are of equal length.

For example, given s = "egg" and t = "add", the answer is true (e maps to a, g maps to d). For s = "foo" and t = "bar", the answer is false.

Thought Process

To solve this problem, we first need to understand what it means for two strings to be isomorphic. The key is to ensure a unique and consistent mapping from each character in s to a character in t, and vice versa.

A brute-force approach might try all possible mappings, but this quickly becomes infeasible for longer strings due to the number of possible permutations. Instead, we realize that we can efficiently check for isomorphism by tracking the mapping as we iterate through both strings.

The main insight is that we need to check two things:

• If a character in s has been mapped before, it must always map to the same character in t.
• No two different characters in s map to the same character in t (one-to-one mapping).

Solution Approach

• Step 1: Check if the lengths of s and t are the same. If not, return false.
• Step 2: Initialize two empty hash maps (dictionaries): one for mapping from s to t, and another for mapping from t to s. These help ensure that the mapping is one-to-one and consistent in both directions.
• Step 3: Iterate through both strings at the same time, character by character.
  • For each pair of characters (c1 from s and c2 from t):
  • If c1 has been seen before in the s-to-t map, check that it maps to c2. If not, return false.
  • If c2 has been seen before in the t-to-s map, check that it maps to c1. If not, return false.
  • If neither mapping exists yet, add both mappings: c1 to c2 and c2 to c1.
• Step 4: If the iteration completes without finding any inconsistencies, return true.

Using hash maps ensures that lookups and insertions are fast (O(1) time), making the algorithm efficient even for long strings.

Example Walkthrough

Let's walk through the example s = "paper" and t = "title" step by step:

1. Initialize two empty maps: s_to_t = {}, t_to_s = {}.
2. First pair: p and t.
   • Neither is mapped yet. Add p → t and t → p.
3. Second pair: a and i.
   • Neither is mapped yet. Add a → i and i → a.
4. Third pair: p and t.
   • p is already mapped to t and t is mapped to p. OK.
5. Fourth pair: e and l.
   • Neither is mapped yet. Add e → l and l → e.
6. Fifth pair: r and e.
   • Neither is mapped yet. Add r → e and e → r.
7. No conflicts found, so we return true.

If at any step a mapping conflict is found (e.g., p tries to map to both t and l), we immediately return false.

Time and Space Complexity

• Brute-Force Approach:
  • Would involve generating all possible mappings between characters, which is factorial time (very slow, O(n!)).
• Optimized Approach (Hash Map):
  • Time Complexity: O(n), where n is the length of the strings. We only loop through the strings once, and all hash map operations are O(1).
  • Space Complexity: O(n) in the worst case, for storing the mappings if all characters are unique.

Summary

The isomorphic strings problem is efficiently solved by tracking one-to-one mappings between characters in both directions using hash maps. This approach quickly detects any inconsistencies and avoids the need for expensive brute-force methods. The key insight is to ensure that each character in one string maps to only one character in the other, and vice versa, throughout the entire string. This makes the solution both elegant and efficient.