We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Isomorphic Strings

Number: 205

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Yandex, Meta, Microsoft, Remitly, LinkedIn, Bloomberg, Oracle, HashedIn, Tinkoff, Goldman Sachs, Apple, Adobe, Yahoo, eBay, Salesforce, Zoho, TikTok

Problem Description

Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t, keeping the order of characters intact, and ensuring no two characters map to the same character, although a character may map to itself.

Key Insights

  • Use a mapping (dictionary/hash table) from characters in s to characters in t.
  • Use a second mapping from characters in t back to s to ensure a one-to-one correspondence.
  • If any mapping is inconsistent, the strings are not isomorphic.
  • Traverse both strings simultaneously.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings, as we iterate through each character once. Space Complexity: O(1) under the assumption that the character set is fixed (ASCII), otherwise O(n) in the worst case.

Solution

The algorithm iterates over each character pair from s and t. For each pair, it checks two mappings:

  1. If the current character from s has been previously mapped, it must map to the current character in t.
  2. If the current character from t has been previously mapped, it must map to the current character in s. If both conditions are satisfied for all character pairs, then the strings are isomorphic. Data structures used include two dictionaries (or hash tables) to keep track of the mappings from s to t and t to s.

Code Solutions

# Function to check if s and t are isomorphic
def is_isomorphic(s, t):
    # Dictionary to store mapping of characters from s to t
    mapping_st = {}
    # Dictionary to store mapping of characters from t to s
    mapping_ts = {}
    
    # Iterate over characters in s and t concurrently
    for char_s, char_t in zip(s, t):
        # Check mapping from s to t
        if char_s in mapping_st:
            if mapping_st[char_s] != char_t:
                return False
        else:
            mapping_st[char_s] = char_t
        
        # Check mapping from t to s
        if char_t in mapping_ts:
            if mapping_ts[char_t] != char_s:
                return False
        else:
            mapping_ts[char_t] = char_s
    
    return True

# Example usage:
print(is_isomorphic("egg", "add"))   # Output: True
print(is_isomorphic("foo", "bar"))   # Output: False
print(is_isomorphic("paper", "title"))  # Output: True
← Back to All Questions