5 Best Ways to Check if Two Strings are Isomorphic in Python

by

💡 Problem Formulation: Determining if two strings are isomorphic in python involves checking whether the characters in one string can be replaced to get the other string, while preserving the order of characters. No two characters may map to the same character, but a character may map to itself. For example: “egg” and “add” are isomorphic, but “foo” and “bar” are not.

Method 1: Using a Dictionary to Store Mappings

This method checks for isomorphism by creating a dictionary to store character mappings from one string to another. Two strings are isomorphic if the character mappings are consistent throughout.

Here’s an example:

def are_isomorphic(str1, str2):
    if len(str1) != len(str2):
        return False
    mapping = {}
    for char1, char2 in zip(str1, str2):
        if char1 in mapping:
            if mapping[char1] != char2:
                return False
        else:
            if char2 in mapping.values():
                return False
            mapping[char1] = char2
    return True

# Testing the function
print(are_isomorphic('paper', 'title'))

Output: True

This code snippet defines a function are_isomorphic() that maps each character from the first string to the second. It returns False if a mismatch is found or if a character from the second string is already mapped to a different character from the first string. If all characters are consistently mapped, it returns True.

Method 2: One-Pass with Two Dictionaries

In this approach, two dictionaries are used to ensure that no two characters from either string are mapped to the same character. Each step verifies the mapping in both directions for a character pair.

Here’s an example:

def are_isomorphic(str1, str2):
    if len(str1) != len(str2):
        return False
    map_str1_to_str2, map_str2_to_str1 = {}, {}
    for char1, char2 in zip(str1, str2):
        if (char1 not in map_str1_to_str2) and (char2 not in map_str2_to_str1):
            map_str1_to_str2[char1] = char2
            map_str2_to_str1[char2] = char1
        elif map_str1_to_str2.get(char1) != char2 or map_str2_to_str1.get(char2) != char1:
            return False
    return True

# Testing the function
print(are_isomorphic('egg', 'add'))

Output: True

The code defines are_isomorphic(), which uses dual mappings to check the isomorphism condition. It considers both direction of mapping to be valid, ensuring that a character in either string doesn’t relate to more than one character in the other string. This method prevents conflicts and is efficient because it runs in linear time.

Method 3: Set and List Based Verification

Using sets and lists, this method compares the pattern of character occurrences in both strings. If the patterns match, the strings are isomorphic. The transformation from each string to a list of character indices is compared.

Here’s an example:

def transform_string(s):
    index_map = {}
    return [index_map.setdefault(c, len(index_map)) for c in s]

def are_isomorphic(str1, str2):
    return transform_string(str1) == transform_string(str2)

# Testing the function
print(are_isomorphic('foo', 'bar'))

Output: False

The function transform_string() generates a list of indices for each string which represents the pattern of character occurrences. are_isomorphic() simply checks the equivalence of these lists for the two strings. This method works well with strings of equal length and where order-preserving mapping is required.

Method 4: Using ASCII Value Differences

This technique verifies that the difference in ASCII values for corresponding characters of the two strings remains consistent throughout. Strings with consistent ASCII value differences are isomorphic.

Here’s an example:

def are_isomorphic(str1, str2):
    if len(str1) != len(str2):
        return False
    diff_set = set()
    for char1, char2 in zip(str1, str2):
        diff_set.add(ord(char1) - ord(char2))
    return len(diff_set) == 1

# Testing the function
print(are_isomorphic('abc', 'bcd'))

Output: True

The function are_isomorphic() compares the ASCII values differences between each character pair using Python’s built-in ord() function. If the set of differences contains only one unique value, the strings are considered isomorphic. However, the validity of this approach depends on the strings having a consistent character offset.

Bonus One-Liner Method 5: Using Functional Programming

A one-liner approach leveraging Python’s functional programming with map and zip functions to compare the structure of the two strings.

Here’s an example:

are_isomorphic = lambda str1, str2: len(set(zip(str1, str2))) == len(set(str1)) == len(set(str2))

# Testing the function
print(are_isomorphic('add', 'egg'))

Output: True

This concise one-liner defines an anonymous function that checks if the number of unique character pairs in the strings (from a zip) equals the number of unique characters in each string. It’s a clever use of Python’s set and lambda functions to achieve a concise form of the isomorphism check.

Summary/Discussion

  • Method 1: Dictionary Mappings. It is a straightforward and understandable method. It may not be the most efficient regarding time complexity.
  • Method 2: Double Dictionary Check. This method is more efficient than the first and equally understandable. However, it requires additional memory overhead for the second dictionary.
  • Method 3: Set and List Comparison. This method provides an abstract way to compare the structure of strings, making it elegant but slightly less intuitive.
  • Method 4: ASCII Value Differences. It has the benefit of being concise but assumes a consistent character offset, which limits its application.
  • Method 5: Functional Programming One-Liner. While being the most concise and potentially the most “Pythonic,” this one-liner may not be as readable for beginners or as self-explanatory as the other methods.