DEV Community

King coder
King coder

Posted on • Edited on

Day 9 and 10 of My DSA Problem Solving Journey

๐Ÿง  Day 9 & Day 10 of My DSA Journey: Cracked the "Isomorphic Strings" Problem After a Lot of Struggle!

This one wasnโ€™t easy โ€” and thatโ€™s what made it worth it.

For the past two days, Iโ€™ve been working on a deceptively tricky problem: Isomorphic Strings.

At first glance, it seems simple. But understanding the logic and finding the right approach took a lot of trial, error, and learning. I struggled on Day 9, revisited the concepts, and finally solved it confidently on Day 10. ๐Ÿ’ช

โœ… Problem 1: Isomorphic Strings

  • ๐Ÿงฉ Can You Consistently Replace Letters to Make Two Strings Match?

  • What if I told you it's possible to judge whether two strings like "egg" and "add" are essentially the sameโ€”if you rename all letters consistently?

Examples

  • "egg" โ†’ "add" โœ…

    (e โ†’ a, g โ†’ d)

  • "foo" โ†’ "bar" โŒ

    (o would have to map to both a and r)

  • "paper" โ†’ "title" โœ…

    (p โ†’ t, a โ†’ i, e โ†’ l, r โ†’ e)

These are called isomorphic strings: you can relabel each character in the first string to get the second, as long as:

  • Each mapping is one-to-one
  • The rule is consistent throughout

๐Ÿ”Ž Problem Statement

Given two strings s and t, determine if they are isomorphic.

Conditions:

  • Both strings must have the same length
  • You can replace each character in s with a corresponding one in t
  • The replacements must be consistent across the entire string
  • No two different characters in s can map to the same character in t

๐Ÿ› ๏ธ Real-World Analogy

Imagine translating an alien language. Each alien character must always translate to one and only one English character. Two different alien characters canโ€™t translate to the same English one. If you can make such a consistent translation for the entire sentence, the two phrases are isomorphic.


Example


Input: num = 12;
Output: The number is positive

Enter fullscreen mode Exit fullscreen mode

Approach


1. **Check the length**  
   - If `len(s) != len(t)`, return `false` immediately.

2. **Create two maps (dictionaries)**  
   - `mapS` to track mappings from `s โ†’ t`  
   - `mapT` to track mappings from `t โ†’ s`

3. **Walk through both strings together**  
   For each index `i`, do the following:

   - Let `cS = s[i]` and `cT = t[i]`
   - Check both maps:
     - If `cS` exists in `mapS` and `mapS[cS] != cT`, return `false`
     - If `cT` exists in `mapT` and `mapT[cT] != cS`, return `false`
   - If all checks pass, add the mappings:
     - `mapS[cS] = cT`
     - `mapT[cT] = cS`

4. **Return true**  
   - If you finish the loop without conflicts, the strings are isomorphic!


Enter fullscreen mode Exit fullscreen mode

Js Code


/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */


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

    let mapS = new Map();
    let mapT = new Map();

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

        // Check if charS is already mapped to a different charT

        if (mapS.has(charS) && mapS.get(charS) !== charT) {
            return false;
        }


        // Check if charT is already mapped to a different charS
        if (mapT.has(charT) && mapT.get(charT) !== charS) {
            return false;
        }

        // Create the mappings
        mapS.set(charS, charT);
        mapT.set(charT, charS);
    }

    return true;
};

console.log(isIsomorphic("egg", "add")); // true
console.log(isIsomorphic("foo", "bar")); // false
console.log(isIsomorphic("paper", "title")); // true
console.log(isIsomorphic("ab", "aa")); // false

Enter fullscreen mode Exit fullscreen mode

Top comments (0)