LeetCode 205: Isomorphic Strings Solution in Python Explained

Problem Statement

In LeetCode 205: Isomorphic Strings, you’re given:

• Two strings s and t of the same length.
• Your task is to return true if they’re isomorphic, false otherwise.

Two strings are isomorphic if the characters in s can be replaced to get t, with each character in s mapping to exactly one character in t, and vice versa. This differs from prime counting in LeetCode 204: Count Primes, focusing instead on string mapping.

Constraints

• 1 ≤ s.length ≤ 5 * 10⁴.
• s.length == t.length.
• s and t contain any valid ASCII characters.

Examples

Let’s see some cases:

Copy codeInput: s = "egg", t = "add"
Output: true
Explanation: 
<ul>
<li>e → a, g → d (one-to-one mapping).</li>
</ul>

Copy codeInput: s = "foo", t = "bar"
Output: false
Explanation: 
<ul>
<li>f → b, o → a, but second o can’t map to r (already mapped to a).</li>
</ul>

Copy codeInput: s = "paper", t = "title"
Output: true
Explanation: 
<ul>
<li>p → t, a → i, e → l, r → e (bijective).</li>
</ul>

These examples show we’re checking for consistent, unique mappings.

Understanding the Problem

How do we solve LeetCode 205: Isomorphic Strings in Python? For s = "egg", t = "add", we map e to a and g to d, and it works because each character pairs uniquely. For s = "foo", t = "bar", f → b and o → a, but the second o can’t map to r—it breaks the one-to-one rule. This isn’t a linked list problem like LeetCode 203: Remove Linked List Elements; it’s about character correspondence. We’ll use: 1. Two Hash Maps: O(n) time, O(k) space—our best solution (k = unique characters). 2. Single Hash Map with Set: O(n) time, O(k) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two Hash Maps Approach

Explanation

The Two Hash Maps approach uses two dictionaries:

• s_to_t: Maps characters in s to t.
• t_to_s: Maps characters in t to s.
• Iterate through both strings simultaneously:
• If a character in s is already mapped, check if it matches the current t character.
• If not mapped, ensure the t character isn’t mapped to another s character, then add mappings.
• If any check fails, return false.

This runs in O(n) time (one pass through the strings) and O(k) space (k = number of unique characters, bounded by ASCII size), making it clear and robust—our best solution.

For s = "egg", t = "add", it builds consistent mappings and returns true.

Step-by-Step Example

Example 1: s = "egg", t = "add"

Goal: Return true.

• Step 1: Initialize.
• s_to_t = {{, t_to_s = {{.
• Step 2: Iterate.
• s[0] = 'e', t[0] = 'a':
• e not in s_to_t, a not in t_to_s.
• s_to_t['e'] = 'a', t_to_s['a'] = 'e'.
• s[1] = 'g', t[1] = 'd':
• g not in s_to_t, d not in t_to_s.
• s_to_t['g'] = 'd', t_to_s['d'] = 'g'.
• s[2] = 'g', t[2] = 'd':
• g in s_to_t, check s_to_t['g'] == 'd' (true), continue.
• Step 3: Finish.
• All mappings consistent, return true.

Example 2: s = "foo", t = "bar"

Goal: Return false.

• Step 1: s_to_t = {{, t_to_s = {{.
• Step 2:
• f, b: s_to_t['f'] = 'b', t_to_s['b'] = 'f'.
• o, a: s_to_t['o'] = 'a', t_to_s['a'] = 'o'.
• o, r: o in s_to_t, but s_to_t['o'] = 'a' != 'r', return false.
• Output: false.

How the Code Works (Two Hash Maps) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef isIsomorphic(s: str, t: str) -> bool:
    # Line 1: Initialize two hash maps
    s_to_t = {{
    # Maps s chars to t chars (e.g., {{)
    t_to_s = {{
    # Maps t chars to s chars (e.g., {{)

    # Line 2: Iterate through strings simultaneously
    for char_s, char_t in zip(s, t):
        # Pair chars (e.g., 'e', 'a')

        # Line 3: Check mapping from s to t
        if char_s in s_to_t:
            # If char_s already mapped (e.g., 'g')
            if s_to_t[char_s] != char_t:
                # Mapping inconsistent (e.g., 'd' != 'r')
                return False
        else:
            # New mapping needed
            if char_t in t_to_s:
                # char_t already mapped to another char_s (e.g., 'a' in t_to_s)
                return False
            s_to_t[char_s] = char_t
            # Set mapping (e.g., 'e' → 'a')
            t_to_s[char_t] = char_s
            # Reverse mapping (e.g., 'a' → 'e')

    # Line 4: All mappings consistent
    return True
    # Return true if isomorphic (e.g., true for "egg", "add")

This solution ensures a bijective mapping efficiently.

Alternative: Single Hash Map with Set Approach

Explanation

The Single Hash Map with Set approach uses one map and a set:

• mapping: Maps s characters to t characters.
• seen: Tracks used t characters.
• If s[i] is mapped, check consistency; if not, ensure t[i] isn’t used, then map it.

It’s O(n) time and O(k) space, offering a concise alternative with similar performance.

Step-by-Step Example

For s = "paper", t = "title":

• p, t: mapping['p'] = 't', seen = {'t'{.
• a, i: mapping['a'] = 'i', seen = {'t', 'i'{.
• p, t: mapping['p'] == 't', continue.
• e, l: mapping['e'] = 'l', seen = {'t', 'i', 'l'{.
• r, e: mapping['r'] = 'e', seen = {'t', 'i', 'l', 'e'{.
• Output: true.

How the Code Works (Single Map)

Copy codedef isIsomorphicSingle(s: str, t: str) -> bool:
    mapping = {{
    seen = set()
    for char_s, char_t in zip(s, t):
        if char_s in mapping:
            if mapping[char_s] != char_t:
                return False
        else:
            if char_t in seen:
                return False
            mapping[char_s] = char_t
            seen.add(char_t)
    return True

Complexity

• Two Hash Maps:
• Time: O(n) – one pass.
• Space: O(k) – two maps (k = unique chars).
• Single Hash Map with Set:
• Time: O(n) – one pass.
• Space: O(k) – one map and set.

Efficiency Notes

Two Hash Maps is our best solution for its clarity and explicit bidirectionality. Single Hash Map with Set is more concise but slightly less intuitive.

Key Insights

• Isomorphic: One-to-one mapping.
• Hash Maps: Track consistency.
• Bidirectionality: Ensures uniqueness.

Additional Example

For s = "badc", t = "baba":

• b → b, a → a, d → b: d can’t map to b (already used), false.

Edge Cases

• s = "a", t = "b": true.
• s = "aa", t = "ab": false.
• Empty strings (not per constraints): Assume true if length matches.

Both handle these well.

Final Thoughts

LeetCode 205: Isomorphic Strings in Python is a great string pattern challenge. Two Hash Maps offers clarity and robustness, while Single Hash Map with Set provides elegance. Want more? Try LeetCode 290: Word Pattern or LeetCode 49: Group Anagrams. Test your skills—Solve LeetCode 205 on LeetCode with s = "egg", t = "add" (expecting true)—map those strings today!