Domain 1EasyCORE

Isomorphic Strings

The problem asks us to determine if two strings `s` and `t` are isomorphic. Two strings are considered isomorphic if the characters in `s` can be replaced to get `t`, with the following conditions: 1. All occurrences of a character in `s` must be replaced with another character while preserving the order. 2. No two characters may map to the same character, but a character may map to itself.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

205. Isomorphic Strings

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 40.6%


Problem Breakdown

The problem asks us to determine if two strings s and t are isomorphic. Two strings are considered isomorphic if the characters in s can be replaced to get t, with the following conditions:

  1. All occurrences of a character in s must be replaced with another character while preserving the order.
  2. No two characters may map to the same character, but a character may map to itself.

Inputs:

  • Two strings s and t.

Outputs:

  • A boolean value indicating whether the strings are isomorphic or not.

Implicit Constraints/Edge Cases:

  • The lengths of s and t are equal.
  • Strings consist of valid ASCII characters.
  • Consider edge cases like empty strings, single-character strings, and strings with all identical characters.

Intuition

A brute-force approach would involve checking every possible mapping from characters in s to characters in t, which is computationally expensive. Instead, we can use a more efficient approach by leveraging hash tables (dictionaries) to track the character mappings between s and t.

The key insight is that for two strings to be isomorphic:

  1. Each character in s must map uniquely to a character in t.
  2. The mapping should be consistent across all occurrences of each character.

Approach

We will use two hash tables (dictionaries) to keep track of the mappings from characters in s to characters in t, and vice versa. As we iterate through the strings, we check if the current characters have a consistent mapping:

  1. If a character from s is already mapped to a different character in t, return False.
  2. If a character from t is already mapped to a different character in s, return False.
  3. If no such inconsistencies are found, the strings are isomorphic.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the strings. We iterate through each string once.
  • Space Complexity: O(1) since the hash tables will store at most 256 entries (one for each possible ASCII character).

Solution

def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    # Dictionaries to store mappings from s to t and t to s
    map_s_to_t = {}
    map_t_to_s = {}
    
    for char_s, char_t in zip(s, t):
        # Check mapping from s to t
        if char_s in map_s_to_t:
            if map_s_to_t[char_s] != char_t:
                return False
        else:
            map_s_to_t[char_s] = char_t
        
        # Check mapping from t to s
        if char_t in map_t_to_s:
            if map_t_to_s[char_t] != char_s:
                return False
        else:
            map_t_to_s[char_t] = char_s
    
    return True

Edge Cases Handled

  • Empty Strings: The function will correctly return True for two empty strings.
  • Single Character Strings: The function will handle single-character strings and return True if they are identical, otherwise False.
  • Strings with All Identical Characters: The function will correctly map identical characters to each other.
  • Different Lengths (though per problem constraints, this won’t occur): The function checks for length equality at the start and returns False immediately if lengths differ.