Top Interview 150

The Isomorphic Strings problem is a string mapping challenge that involves character substitutions while preserving order. Let’s solve LeetCode 205: Isomorphic Strings step by step.

🚀 Problem Description

Two strings s and t are isomorphic if:

• Each character in s can be replaced by a unique character in t.
• The order of characters in s is preserved in t.
• No two characters in s map to the same character in t, and vice versa.

💡 Examples

Example 1

Input: s = "egg", t = "add"  
Output: true  
Explanation: 'e' maps to 'a', 'g' maps to 'd'.

Example 2

Input: s = "foo", t = "bar"  
Output: false  
Explanation: 'o' would need to map to both 'a' and 'r'.

Example 3

Input: s = "paper", t = "title"  
Output: true  
Explanation: 'p' maps to 't', 'a' maps to 'i', etc.

🏆 JavaScript Solution

We solve this problem using two hash maps:

• To map characters from s to t.
• To ensure no two characters in s map to the same character in t.

Implementation

var isIsomorphic = function(s, t) {
    if (s.length !== t.length) return false;

    const mapST = {};
    const mapTS = {};

    for (let i = 0; i < s.length; i++) {
        const charS = s[i];
        const charT = t[i];

        if ((mapST[charS] && mapST[charS] !== charT) || 
            (mapTS[charT] && mapTS[charT] !== charS)) {
            return false;
        }

        mapST[charS] = charT;
        mapTS[charT] = charS;
    }

    return true;
};

🔍 How It Works

1. Check Lengths:

   • If the strings have different lengths, they cannot be isomorphic.

2. Use Two Maps:

   • mapST: Maps characters in s to characters in t.
   • mapTS: Maps characters in t to characters in s.

3. Traverse Characters:

   • For each pair of characters in s and t, check if the mappings are consistent.
   • If not, return false.

4. Return true:

   • If all characters are mapped consistently, the strings are isomorphic.

🔑 Complexity Analysis

• Time Complexity: O(n), where n is the length of s (or t).

  • Each character is processed once.

• Space Complexity: O(1), since the hash maps can store at most 256 entries (ASCII characters).

📋 Dry Run

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

Output: true

✨ Pro Tips for Interviews

1. Edge Cases:

   • Different lengths: s = "abc", t = "ab".
   • Single-character strings: s = "a", t = "a".
   • Repeated characters: s = "aaa", t = "bbb".

2. Discuss Two Maps:

   • Emphasize the need for bidirectional mapping to avoid conflicts.

3. Optimization:

   • Highlight how this approach works in _O(n)_, which is optimal for this problem.

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Ransom Note - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀