๐ง 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 int
- The replacements must be consistent across the entire string
-
No two different characters in
s
can map to the same character int
๐ ๏ธ 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
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!
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
Top comments (0)