Leetcode – Isomorphic Strings Solution in Python

Introduction

The Isomorphic Strings problem is a classic coding question that can be found on LeetCode, a popular platform for practicing coding skills. This problem is an excellent example to understand the concepts of string manipulation and hashing. In this extensive guide, we will dissect the Isomorphic Strings problem, explore different approaches to solve it, and evaluate their efficiencies.

Understanding the Problem

The Isomorphic Strings problem (LeetCode #205) is defined as follows:

Given two strings s and t, return true if s and t are isomorphic. Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example: Input: s = “egg”, t = “add” Output: true

Here, ‘e’ can be replaced with ‘a’ and ‘g’ can be replaced with ‘d’ to transform “egg” to “add”.

Approach 1: Using Two Hash Maps

One way to solve this problem is by using two hash maps to keep track of the mapping from characters in s to characters in t, and vice versa.

def isIsomorphic(s, t):
    # Hash maps to keep track of character mapping
    mapping_st = {}
    mapping_ts = {}
    
    # Iterating through each character in s and t
    for char_s, char_t in zip(s, t):
        # Check if there is a mismatch in the mapping
        if (char_s in mapping_st and mapping_st[char_s] != char_t) or (char_t in mapping_ts and mapping_ts[char_t] != char_s):
            return False
        
        # Update the mappings
        mapping_st[char_s] = char_t
        mapping_ts[char_t] = char_s
    
    # If the loop completes without returning False, the strings are isomorphic
    return True

This approach uses O(n) time and O(n) space, where n is the length of the strings.

Approach 2: Using Single Hash Map and a Set

An optimized version involves using a single hash map for character mapping from s to t, and a set to keep track of characters already mapped in t.

def isIsomorphic(s, t):
    # Hash map and set to keep track of character mapping
    mapping_st = {}
    mapped_chars = set()
    
    # Iterating through each character in s and t
    for char_s, char_t in zip(s, t):
        # Check if there is a mismatch in the mapping
        if char_s in mapping_st:
            if mapping_st[char_s] != char_t:
                return False
        else:
            if char_t in mapped_chars:
                return False
            # Update the mappings
            mapping_st[char_s] = char_t
            mapped_chars.add(char_t)
    
    # If the loop completes without returning False, the strings are isomorphic
    return True

This approach also has a time complexity of O(n) and space complexity of O(n), but uses slightly less space compared to the first approach.

Approach 3: Using Encoding

We can encode both strings based on the index of the first occurrence of each character. If both encodings are equal, the strings are isomorphic.

def isIsomorphic(s, t):
    # Encoding the strings
    encoding_s = [s.index(char) for char in s]
    encoding_t = [t.index(char) for char in t]
    
    # Comparing encodings
    return encoding_s == encoding_t

This approach has a time complexity of O(n^2) due to the use of the index function inside a loop but has a space complexity of O(1).

Testing the Solutions

You can test any of the above solutions by calling the function with the input strings.

# Example
s = "paper"
t = "title"
print(isIsomorphic(s, t))  # Output: True

Conclusion

The Isomorphic Strings problem is a classic example to understand hash maps and string encoding. We discussed three approaches with varying time and space complexities. In practice, the choice of approach depends on the constraints and requirements of the problem you are solving.