205. Isomorphic Strings - Detailed Explanation

Problem Statement

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 with a one-to-one mapping between characters. All occurrences of a character must be replaced with another character while preserving the order. No two characters may map to the same character, but a character may map to itself.

Example Inputs/Outputs and Explanations

Example 1

• Input: s = "egg", t = "add"
• Output: true
• Explanation: 'e' maps to 'a' and 'g' maps to 'd'. Both occurrences of 'g' map consistently to 'd'.

Example 2

• Input: s = "foo", t = "bar"
• Output: false
• Explanation: 'f' would map to 'b', but 'o' appears twice in s while in t the corresponding characters are 'a' and 'r', which are not the same.

Example 3

• Input: s = "paper", t = "title"
• Output: true
• Explanation: A valid mapping is: 'p' → 't', 'a' → 'i', 'e' → 'l', 'r' → 'e'. Notice that 'p' appears twice and consistently maps to 't'.

Constraints

• The lengths of s and t are the same.
• Both s and t consist of printable ASCII characters.
• The maximum length could be up to 10^5 characters.

Hints Before the Solution

• Think about how you can maintain a mapping between characters of s and t. Consider using a dictionary (or hashmap) to store these mappings.
• Remember to verify that the mapping is one-to-one. This means you must also ensure that no two characters in s map to the same character in t.
• Check the mapping in both directions—mapping from s to t and from t to s—to handle cases where a character might be assigned to multiple characters.

Brute Force Approach (Conceptual and Inefficient)

One brute force method is to try every possible mapping between the characters in s and t and check if any valid mapping exists. For example, you could generate every permutation for characters in t and check if replacing the characters in s gives you t.
Drawbacks:

• The number of possible mappings grows exponentially with the number of unique characters.
• This approach quickly becomes impractical even for moderate string lengths.

Optimal Approach: Two Hash Maps (or Dictionaries)

A far more efficient solution involves using two dictionaries:

• One dictionary maps characters from s to t.
• The other maps characters from t to s.

Algorithm Steps:

• If the strings are of different lengths, return false immediately.
• Iterate over both strings simultaneously.
  • For each pair of characters (char_s, char_t):
    • If char_s is already mapped, check if it maps to char_t.
    • Similarly, if char_t is already mapped, verify that it maps to char_s.
    • If either check fails, return false.
    • Otherwise, record the mapping in both dictionaries.
• If the entire iteration completes without conflict, return true.

Alternative with Fixed-Size Arrays

If you know that the input strings use a limited character set (like ASCII), you can use two arrays of size 256 instead of dictionaries. Each array index corresponds to a character, allowing constant-time lookup.

Step-by-Step Walkthrough with a Visual Example

Consider the strings: s = "paper" and t = "title".

• Iteration 1:
  • s[0] = 'p', t[0] = 't'.
  • No mapping exists. Set mapping: 'p' → 't' and 't' → 'p'.
• Iteration 2:
  • s[1] = 'a', t[1] = 'i'.
  • Set mapping: 'a' → 'i' and 'i' → 'a'.
• Iteration 3:
  • s[2] = 'p', t[2] = 't'.
  • Check: The mapping for 'p' already exists and is 't'. This is consistent.
• Iteration 4:
  • s[3] = 'e', t[3] = 'l'.
  • Set mapping: 'e' → 'l' and 'l' → 'e'.
• Iteration 5:
  • s[4] = 'r', t[4] = 'e'.
  • Set mapping: 'r' → 'e' and 'e' → 'r'.

At the end of the iterations, no inconsistencies are found, so the strings are isomorphic.

Complexity Analysis

• Time Complexity: O(n) — Each character in the strings is processed once.
• Space Complexity: O(n) (or O(1) if using fixed-size arrays for a limited character set) — In the worst case, every character has a unique mapping, so the dictionaries will store up to n key-value pairs.

Common Mistakes and Edge Cases

• Ignoring Reverse Mapping: Failing to check the mapping from t to s can lead to incorrect results where two different characters in s map to the same character in t.
• Different String Lengths: Always check if the lengths of s and t are equal before processing.
• Repeated Characters: Not verifying that repeated characters in s consistently map to the corresponding characters in t.
• Edge Case: Empty strings are trivially isomorphic. If both strings are empty, the answer is true.

Python Code Implementation