LeetCode 205: Isomorphic Strings - All Solutions Explained

Problem Statement

The Isomorphic Strings problem, LeetCode 205, is an easy-difficulty challenge that requires determining if two strings are isomorphic. Two strings are isomorphic if the characters in one string can be replaced to get the other string while preserving the order of characters. All occurrences of a character must be replaced with another character while maintaining the character mapping consistency.

Copy codeInput: s = "egg", t = "add"
Output: true
Explanation: e → a, g → d (consistent mapping)

Input: s = "foo", t = "bar"
Output: false
Explanation: f → b, o → a is possible for first two characters, but o cannot map to both a and r

Input: s = "paper", t = "title"
Output: true
Explanation: p → t, a → i, e → l, r → e

Solution 1: Two Hash Maps (Best Solution)

Explanation of the Best Solution

This approach uses two dictionaries to track the character mappings in both directions (s→t and t→s).

1. Initialize two dictionaries: One for s→t mapping, another for t→s mapping
2. Iterate through characters:
3. If s_char exists in s_map, verify it maps to current t_char
4. If t_char exists in t_map, verify it maps to current s_char
5. If either check fails, strings aren't isomorphic
6. If checks pass, create new mappings
7. Return true if all characters are processed without conflicts

Step-by-Step Example

For s = "egg", t = "add": 1. e not in s_map, a not in t_map → map e→a and a→e 2. g not in s_map, d not in t_map → map g→d and d→g 3. g in s_map maps to d (matches current t_char) → continue Result: true

For s = "foo", t = "bar": 1. f not in s_map, b not in t_map → map f→b and b→f 2. o not in s_map, a not in t_map → map o→a and a→o 3. o in s_map maps to a but current t_char is r → conflict → false

Python Code (Two Hash Maps)

Copy codedef isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    s_to_t = {}
    t_to_s = {}

    for s_char, t_char in zip(s, t):
        # Check existing mappings
        if s_char in s_to_t:
            if s_to_t[s_char] != t_char:
                return False
        else:
            s_to_t[s_char] = t_char

        if t_char in t_to_s:
            if t_to_s[t_char] != s_char:
                return False
        else:
            t_to_s[t_char] = s_char

    return True

Complexity

• Time Complexity: O(n) - single pass through both strings
• Space Complexity: O(1) - fixed space for ASCII character mappings (max 256 entries per map)

Why It's the Best

• Clear and straightforward logic
• Handles all edge cases properly
• Optimal time and space complexity
• Easy to understand and implement in interviews

Solution 2: Index Comparison

Explanation

This clever approach compares the first occurrence indices of each character in both strings.

1. Create two dictionaries: Track first occurrence indices of characters
2. Compare positional patterns:
3. If the indices of corresponding characters differ, strings aren't isomorphic
4. Uses the fact that isomorphic strings must have identical character patterns

Step-by-Step Example

For s = "paper", t = "title": - s indices: p→0, a→1, p→0, e→3, r→4 → [0,1,0,3,4] - t indices: t→0, i→1, t→0, l→3, e→4 → [0,1,0,3,4] - Patterns match → true

Python Code (Index Comparison)

Copy codedef isIsomorphic(s: str, t: str) -> bool:
    return [s.index(c) for c in s] == [t.index(c) for c in t]

Complexity

• Time Complexity: O(n²) - index() is O(n) called n times
• Space Complexity: O(n) - storing index lists

Pros and Cons

• Pros: Extremely concise code
• Cons: Poor time complexity for large strings

Solution 3: Single Hash Map with Set

Explanation

This optimized version uses one hash map for s→t mapping and a set to track already mapped t characters.

1. Initialize map and set
2. Iterate through characters:
3. If s_char exists in map, verify mapping matches t_char
4. If s_char is new, verify t_char hasn't been mapped by another s_char
5. Create new mapping if valid
6. Return true if all mappings are consistent

Python Code (Single Map with Set)

Copy codedef isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    char_map = {}
    mapped_chars = set()

    for s_char, t_char in zip(s, t):
        if s_char in char_map:
            if char_map[s_char] != t_char:
                return False
        else:
            if t_char in mapped_chars:
                return False
            char_map[s_char] = t_char
            mapped_chars.add(t_char)

    return True

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) (limited by ASCII charset)

When to Use

• When you want to optimize space slightly
• When you prefer tracking used characters explicitly

Edge Cases to Consider

• Strings of different lengths → immediately false
• All characters same in one string ("aaa", "bbb") → true
• All characters unique ("abc", "def") → true
• Complex mappings ("abab", "cdcd") → true
• Conflict mappings ("ab", "aa") → false

Final Thoughts

• Two Hash Maps: Best overall solution - optimal and clear
• Index Comparison: Clever but inefficient - good for small strings
• Single Map with Set: Slightly optimized version of the best solution

For interviews, the two hash map solution is strongly recommended as it demonstrates clear understanding of the problem constraints.