DEV Community

Cover image for LeetCode Challenge: 205. Isomorphic Strings - JavaScript Solution ๐Ÿš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

3 1 1 1 1

LeetCode Challenge: 205. Isomorphic Strings - JavaScript Solution ๐Ÿš€

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'.
Enter fullscreen mode Exit fullscreen mode

Example 2

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

Example 3

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

๐Ÿ† 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;
};
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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"
Dry Run

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! ๐Ÿš€


Study

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (3)

Collapse
 
subtitleedit profile image
Subtitle Edit โ€ข

The LeetCode challenge "205. Isomorphic Strings" requires you to check if two strings can be transformed into each other by applying a one-to-one character mapping. In JavaScript, a good approach is to use two hash maps to keep track of the character mappings from one string to the other. If a conflict arises during the mapping, the strings are not isomorphic. If youโ€™re optimizing your solution or handling multiple inputs, tools like SubtitleEdit can help you manage and sync data or comments across different code sections for better clarity.

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal โ€ข

Follow Me on GitHub ๐Ÿš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

๐Ÿ‘‹ Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay