Isomorphic Strings

Difficulty: Easy | Acceptance: 48.30% | Paid: No Topics: Hash Table, String

Given two strings s and t, determine if they 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.

• Examples
• Constraints
• Brute Force
• Two Hash Maps
• Array Mapping

Examples

Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

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

Constraints

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

Brute Force

Intuition For every character in the string s, we check all previous characters to ensure the mapping to t is consistent and unique.

Steps

• Iterate through the strings from left to right.
• For each index i, check all previous indices j from 0 to i-1.
• If s[i] is equal to s[j], then t[i] must be equal to t[j].
• If s[i] is not equal to s[j], then t[i] must not be equal to t[j].
• If any condition fails, return false. If the loop finishes, return true.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        n = len(s)
        for i in range(n):
            for j in range(i):
                if s[i] == s[j] and t[i] != t[j]:
                    return False
                if s[i] != s[j] and t[i] == t[j]:
                    return False
        return True

Complexity

• Time: O(n²) where n is the length of the string.
• Space: O(1)
• Notes: This approach is inefficient for large inputs but demonstrates the logic clearly.

Two Hash Maps

Intuition We use two hash maps (dictionaries) to store the mapping from characters of s to t and from t to s. This ensures a one-to-one relationship.

Steps

• Create two empty dictionaries: mapST and mapTS.
• Iterate through the strings simultaneously.
• If the character s[i] is in mapST, check if it maps to t[i]. If not, return false.
• If the character t[i] is in mapTS, check if it maps to s[i]. If not, return false.
• If neither is present, record the mappings s[i] -> t[i] and t[i] -> s[i].
• If the loop completes, return true.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        map_st = {}
        map_ts = {}
        
        for c1, c2 in zip(s, t):
            if c1 in map_st:
                if map_st[c1] != c2:
                    return False
            else:
                map_st[c1] = c2
            
            if c2 in map_ts:
                if map_ts[c2] != c1:
                    return False
            else:
                map_ts[c2] = c1
                
        return True

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) because the character set is fixed (ASCII), though technically O(k) where k is the size of the character set.
• Notes: This is the standard optimal solution for general cases.

Array Mapping

Intuition Since the problem states strings consist of valid ASCII characters, we can use fixed-size arrays (size 256 or 128) instead of hash maps. This reduces overhead and improves performance.

Steps

• Initialize two integer arrays of size 256 (for extended ASCII) with a default value (e.g., -1 or 0).
• Iterate through the strings.
• Check if the mapping stored at the ASCII value of s[i] matches the ASCII value of t[i].
• Check if the reverse mapping stored at the ASCII value of t[i] matches the ASCII value of s[i].
• Update the arrays with the current mappings.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Using lists of size 256 for extended ASCII
        map_st = [-1] * 256
        map_ts = [-1] * 256
        
        for i in range(len(s)):
            c1 = ord(s[i])
            c2 = ord(t[i])
            
            if map_st[c1] != -1 and map_st[c1] != c2:
                return False
            if map_ts[c2] != -1 and map_ts[c2] != c1:
                return False
                
            map_st[c1] = c2
            map_ts[c2] = c1
            
        return True

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) as the array size is fixed regardless of input size.
• Notes: This is often the fastest solution in practice due to cache locality and lack of hashing overhead.