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)