Isomorphic Strings
On this page 
Problem Statement Solution 1: Basic Hash Map Approach Solution 2: Single Hash Map Approach Solution 3: Two Pass Hash Map Approach Solution 4: Character Mapping Arrays Solution 5: One Pass Hash Map Solution 6: Array Index Mapping Solution 7: Hash Map with String Comparison Solution 8: Bi-directional Hash Map Approach Solution 9: Character Mapping with Set More Problems Solutions
Problem Statement
Imagine you have two strings, s and t, and you want to know if you can make them identical by replacing each character in s with a character in t. The catch is that each character in s must map to a single character in t, and no two characters in s can map to the same character in t. Additionally, a character in s can map to itself.
Example 1
Input: s = "egg" , t = "add"
Output: true
Example 2
Input: s = "foo" , t = "bar"
Output: false
Solution 1: Basic Hash Map Approach
function areIsomorphic_BasicHashMap(s, t) {
if (s.length !== t.length) return false;
const mapSToT = {};
const mapTToS = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (mapSToT[charS] === undefined) {
mapSToT[charS] = charT;
} else if (mapSToT[charS] !== charT) {
return false;
}
if (mapTToS[charT] === undefined) {
mapTToS[charT] = charS;
} else if (mapTToS[charT] !== charS) {
return false;
}
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_BasicHashMap(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_BasicHashMap(s2,t2); //output: false
Solution 2: Single Hash Map Approach
function areIsomorphic_SingleHashMap(s, t) {
if (s.length !== t.length) return false;
const map = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (map[charS] === undefined) {
map[charS] = charT;
} else if (map[charS] !== charT) {
return false;
}
}
const reversedMap = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (reversedMap[charT] === undefined) {
reversedMap[charT] = charS;
} else if (reversedMap[charT] !== charS) {
return false;
}
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_SingleHashMap(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_SingleHashMap(s2,t2); //output: false
Solution 3: Two Pass Hash Map Approach
function areIsomorphic_TwoPassHashMap(s, t) {
if (s.length !== t.length) return false;
const mapSToT = {};
const mapTToS = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (mapSToT[charS] !== undefined && mapSToT[charS] !== charT) {
return false;
}
if (mapTToS[charT] !== undefined && mapTToS[charT] !== charS) {
return false;
}
mapSToT[charS] = charT;
mapTToS[charT] = charS;
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_TwoPassHashMap(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_TwoPassHashMap(s2,t2); //output: false
Solution 4: Character Mapping Arrays
function areIsomorphic_CharArrays(s, t) {
if (s.length !== t.length) return false;
const mapS = Array(256).fill(-1);
const mapT = Array(256).fill(-1);
for (let i = 0; i < s.length; i++) {
const charS = s.charCodeAt(i);
const charT = t.charCodeAt(i);
if (mapS[charS] === -1 && mapT[charT] === -1) {
mapS[charS] = charT;
mapT[charT] = charS;
} else if (mapS[charS] !== charT || mapT[charT] !== charS) {
return false;
}
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_CharArrays(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_CharArrays(s2,t2); //output: false
Solution 5: One Pass Hash Map
function areIsomorphic_OnePass(s, t) {
if (s.length !== t.length) return false;
const sToT = {};
const tToS = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if ((sToT[charS] && sToT[charS] !== charT) ||
(tToS[charT] && tToS[charT] !== charS)) {
return false;
}
sToT[charS] = charT;
tToS[charT] = charS;
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_OnePass(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_OnePass(s2,t2); //output: false
Solution 6: Array Index Mapping
function areIsomorphic_ArrayIndexMapping(s, t) {
if (s.length !== t.length) return false;
const sMap = Array(256).fill(-1);
const tMap = Array(256).fill(-1);
for (let i = 0; i < s.length; i++) {
const sIndex = s.charCodeAt(i);
const tIndex = t.charCodeAt(i);
if (sMap[sIndex] === -1 && tMap[tIndex] === -1) {
sMap[sIndex] = tIndex;
tMap[tIndex] = sIndex;
} else if (sMap[sIndex] !== tIndex || tMap[tIndex] !== sIndex) {
return false;
}
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_ArrayIndexMapping(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_ArrayIndexMapping(s2,t2); //output: false
Solution 7: Hash Map with String Comparison
function areIsomorphic_HashMapStringComparison(s, t) {
if (s.length !== t.length) return false;
const sToT = new Map();
const tToS = new Map();
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (sToT.get(charS) !== undefined && sToT.get(charS) !== charT) {
return false;
}
if (tToS.get(charT) !== undefined && tToS.get(charT) !== charS) {
return false;
}
sToT.set(charS, charT);
tToS.set(charT, charS);
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_HashMapStringComparison(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_HashMapStringComparison(s2,t2); //output: false
Solution 8: Bi-directional Hash Map Approach
function areIsomorphic_BiDirectionalHashMap(s, t) {
if (s.length !== t.length) return false;
const mapSToT = {};
const mapTToS = {};
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (mapSToT[charS] === undefined && mapTToS[charT] === undefined) {
mapSToT[charS] = charT;
mapTToS[charT] = charS;
} else if (mapSToT[charS] !== charT || mapTToS[charT] !== charS) {
return false;
}
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_BiDirectionalHashMap(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_BiDirectionalHashMap(s2,t2); //output: false
Solution 9: Character Mapping with Set
function areIsomorphic_Set(s, t) {
if (s.length !== t.length) return false;
const mapSToT = new Map();
const mapTToS = new Map();
for (let i = 0; i < s.length; i++) {
const charS = s[i];
const charT = t[i];
if (mapSToT.has(charS) && mapSToT.get(charS) !== charT) return false;
if (mapTToS.has(charT) && mapTToS.get(charT) !== charS) return false;
mapSToT.set(charS, charT);
mapTToS.set(charT, charS);
}
return true;
}
const s1 = "egg";
const t1 = "add";
areIsomorphic_Set(s1,t1); //output: true
const s2 = "foo";
const t2 = "bar";
areIsomorphic_Set(s2,t2); //output: false