Check if two given strings are ispmorphic

0 / 198
isomorphic strings

Problem statement:-

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

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

 

 

Example 1:

         Input: s = “egg”,      t = “add” Output: true

Example 2:

         Input: s = “foo”,       t = “bar” Output: false

Example 3:

         Input: s = “paper”,    t = “title” Output: true

 

 

 

Note:
You may assume both and have the same length.

 

 

Algorithm for the same in Javascript:-

 

  • Prepare a map of characters and the respective indices on which they occur.

 

  • If the string lengths don’t match or the number of keys in both the maps don’t match return false.

 

  • Sum the frequencies of characters by looping through the respective maps and also concatenate the frequencies of each of the characters in both strings resulting in strings of character frequencies occurring in order.

 

  • Compare strings containing the sum of the frequencies and the character frequencies and return true if either of these match

 

 

Code written in Javascript below:-

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/

var isIsomorphic = function(s, t) {
var patternMap = {}, strMap = {};
var strArr = t.split('');
var patOccurance = '', strOccurance = '';
var patOccuranceVal = '', strOccuranceVal = '';

if (strArr.length !== s.length) return false;

for (var i = 0; i < s.length; i++) {
    if (typeof patternMap[s[i]] === 'undefined')
     patternMap[s[i]] = [];

    if (typeof strMap[strArr[i]] === 'undefined')
     strMap[strArr[i]] = [];

    patternMap[s[i]].push(i);
    strMap[strArr[i]] .push(i);
}

if (Object.keys(patternMap).length !== Object.keys(strMap).length) return false;

for (var key in patternMap) {
    patOccurance += patternMap[key].join('').length;
    patOccuranceVal += patternMap[key].join('');
}

for (var skey in strMap) {
    strOccurance += strMap[skey].join('').length;
    strOccuranceVal += strMap[skey].join('');
}

// console.log(patOccurance, patOccuranceVal, strOccurance, strOccuranceVal);


if (patOccuranceVal.length !== patOccurance.length) {
    return (patOccuranceVal === strOccuranceVal);
}

else
    return (patOccurance === strOccurance) || (patOccuranceVal === strOccuranceVal);
};

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts