Isomorphic Strings | Leetcode 205 | Optimal Hash Map Solution

The Isomorphic Strings problem asks us to determine if two strings s and t are isomorphic.

Two strings are isomorphic if the characters in one string can be replaced to get the other string, while maintaining the following conditions:

1. Each character in s must map to exactly one character in t.
2. No two characters in s can map to the same character in t.
3. The mapping must be consistent across the entire string.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: s = "egg", t = "add"
Output: true
Explanation: 'e' → 'a', 'g' → 'd'.

Example 2

Input: s = "foo", t = "bar"
Output: false
Explanation: 'o' would need to map to both 'o' and 'r', which is not possible.

Example 3

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

Intuition and Approach

The key to solving Isomorphic Strings is checking for consistent one-to-one mappings between the characters of s and t.

1. Use two dictionaries (hash maps):
   • map_s_to_t: maps characters of s to characters of t.
   • map_t_to_s: maps characters of t back to characters of s.
2. For every index i:
   • If s[i] already maps to a character in t, check if it is consistent.
   • If t[i] already maps to a character in s, check consistency in the reverse direction.
   • If either mapping is inconsistent, return False.
3. If the loop finishes without conflicts, the strings are isomorphic.

This ensures bidirectional consistency, which is critical: no two characters in one string can map to the same character in the other.

Code Implementation

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Dictionaries to store the mappings
        map_s_to_t = {}
        map_t_to_s = {}
        
        for i in range(len(s)):
            char_s = s[i]
            char_t = t[i]
            
            # Check if there's already a mapping for char_s in map_s_to_t
            if char_s in map_s_to_t:
                if map_s_to_t[char_s] != char_t:  # Inconsistent mapping
                    return False
            else:
                map_s_to_t[char_s] = char_t
            
            # Check if there's already a mapping for char_t in map_t_to_s
            if char_t in map_t_to_s:
                if map_t_to_s[char_t] != char_s:  # Inconsistent mapping
                    return False
            else:
                map_t_to_s[char_t] = char_s
        
        return True

Code Explanation

• map_s_to_t: ensures each character in s maps to only one character in t.
• map_t_to_s: ensures no two characters in s map to the same character in t.
• For each character pair (char_s, char_t):
  • If mapping exists, check consistency.
  • If no mapping exists, add it.
• If all mappings are consistent, return True; otherwise return False.

Dry Run Example

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

• i = 0: 'p' → 't', add mapping both ways.
• i = 1: 'a' → 'i', add mapping both ways.
• i = 2: 'p' → already mapped to 't', consistent.
• i = 3: 'e' → 'l', add mapping.
• i = 4: 'r' → 'e', add mapping.

All mappings consistent → return True.

Time and Space Complexity

• Time Complexity:
  Loop runs once for each character → O(N), where N = length of the strings.
• Space Complexity:
  Two hash maps storing at most all unique characters → O(K), where K is the character set size (at most 256 for extended ASCII, 26 for lowercase alphabets).

Conclusion

The Isomorphic Strings problem can be solved efficiently using two hash maps to track character mappings both ways.

• Ensures one-to-one correspondence between characters.
• Detects inconsistencies early.
• Runs in linear time with minimal extra space.

This is a common interview problem that tests string mapping and hash map usage, and mastering it will make handling bijection problems much easier.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.