205. Isomorphic Strings - Explanation

Problem Link

Description

You are 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.

Example 1:

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

Output: true

Explanation: The strings s and t can be made identical by:

• Mapping 'e' to 'a'.
• Mapping 'g' to 'd'.

Example 2:

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

Output: false

Explanation: The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Example 3:

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

Output: true

Constraints:

• 0 <= s.length == t.length <= 50,000
• s and t consist of any valid ascii character.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Hash Map (Two Pass)

Intuition

Two strings are isomorphic if there's a one-to-one mapping between their characters. We need to ensure that each character in s maps to exactly one character in t, and vice versa. A single pass checking only s -> t mapping isn't enough because two different characters in s could map to the same character in t. By running the check twice (once for (s, t) and once for (t, s)), we guarantee the mapping is bijective.

Algorithm

1. Create a helper function that checks if characters from one string map consistently to another:
   • Use a hash map to store the character mappings.
   • For each character, check if an existing mapping conflicts with the current pair.
2. Call the helper twice: once with (s, t) and once with (t, s).
3. Return true only if both checks pass.

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

    def isIsomorphic(self, s: str, t: str) -> bool:
        return self.helper(s, t) and self.helper(t, s)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(m)$

Where $n$ is the length of the input string and $m$ is the number of unique characters in the strings.

---

2. Hash Map (One Pass)

Intuition

We can verify both mapping directions simultaneously in a single pass. By maintaining two hash maps, one for s -> t and one for t -> s, we check at each position that neither mapping is violated. If a character in s was previously mapped to a different character in t, or if a character in t was previously mapped to a different character in s, the strings aren't isomorphic.

Algorithm

1. Create two hash maps: mapST for s -> t and mapTS for t -> s.
2. Iterate through both strings simultaneously:
   • If s[i] already maps to something other than t[i], return false.
   • If t[i] already maps to something other than s[i], return false.
   • Otherwise, record both mappings.
3. If the loop completes without conflicts, return true.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapST, mapTS = {}, {}

        for i in range(len(s)):
            c1, c2 = s[i], t[i]
            if ((c1 in mapST and mapST[c1] != c2) or
                (c2 in mapTS and mapTS[c2] != c1)):
                return False
            mapST[c1] = c2
            mapTS[c2] = c1

        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(m)$

Where $n$ is the length of the input string and $m$ is the number of unique characters in the strings.