Check if a given string is a isomorphic

user_7311625 0
Viewed 1464

I found this paragraph and I want to implement it in JS:

For two strings to be isomorphic, all occurrences of a character in string A can be replaced with another character to get string B. The order of the characters must be preserved. There must be one-to-one mapping for every char of string A to every char of string B.

paper and title would return true. egg and sad would return false. dgg and add would return true.

Here's my attempt:

console.log(isIsomorphic("egg", 'add')); // true
console.log(isIsomorphic("paper", 'title')); // true
console.log(isIsomorphic("kick", 'side')); // false

function isIsomorphic(firstString, secondString) {

  // Check if the same lenght. If not, they cannot be isomorphic
  if (firstString.length == secondString.length)
    return false

  var letterMap = {};

  for (var i = 0; i < firstString.length; i++) {
    var letterA = firstString[i],
      letterB = secondString[i];

    // If the letter does not exist, create a map and map it to the value
    // of the second letter
    if (letterMap[letterA] === undefined) {
      letterMap[letterA] = letterB;
    } else if (letterMap[letterA] !== letterB) {
      // Eles if letterA already exists in the map, but it does not map to
      // letterB, that means that A is mapping to more than one letter.
      return false;
    }
  }
  // If after iterating through and conditions are satisfied, return true.
  // They are isomorphic
  return true;
}

I'm confused as to why there is an error in it.

algorithm javascript
2 Answers

You have a simple typo:

  if (firstString.length == secondString.length) {
    return false
  }

You're returning false if the two strings are the same length. Change it to:

  if (firstString.length !== secondString.length) {
    return false
  }


console.log(isIsomorphic("egg", 'add')); // true
console.log(isIsomorphic("paper", 'title')); // true
console.log(isIsomorphic("kick", 'side')); // false

function isIsomorphic(firstString, secondString) {

  // Check if the same lenght. If not, they cannot be isomorphic
  if (firstString.length !== secondString.length) {
    return false
  }

  var letterMap = {};

  for (var i = 0; i < firstString.length; i++) {
    var letterA = firstString[i],
      letterB = secondString[i];

    // If the letter does not exist, create a map and map it to the value
    // of the second letter
    if (letterMap[letterA] === undefined) {
      letterMap[letterA] = letterB;
    } else if (letterMap[letterA] !== letterB) {
      // Eles if letterA already exists in the map, but it does not map to
      // letterB, that means that A is mapping to more than one letter.
      return false;
    }
  }
  // If after iterating through and conditions are satisfied, return true.
  // They are isomorphic
  return true;
}

user_62433520

Your solution is almost correct, ggorlen has shown you the fix. I will, however, give you another solution, which seems to be more elegant to me. Let's introduce the concept of isomorphical signature, which would be a string, which will be similar for all strings which are isomorphic with each other.

Examples:

paper: 0,2;1;3;4

title: 0;2;1;3;4

egg: 0;1,2

sad: 0;1;2

dgg: 0;1,2

add: 0;1,2

The idea is to show the indexes of letters, in their appearance order. The p in paper is on indexes 0 and 2. The a is on index 1. The e is on index 3. The r is on index 4. Let's implement the function which gets the isomorphic signature:

function getIsomorphicSignature(input) {
    var helper = {};
    for (var i = 0; i < input.length; i++) {
        if (!helper[input[i]]) helper[input[i]] = [];
        helper[input[i]].push(i);
    }
    var output = [];
    for (var item in helper) output.push(helper[item].join(","));
    return output.join(";");
}

Now, if you want to see whether two strings are isomorphic, then you can compare their isomorphic signatures. The elegancy of this solution lies in the fact that you have a storable attribute which says a lot of the string in terms of such comparisons. For instance, if you want to group isomorphic strings into clusters, then you can do something like this:

function clusterize(var inputStrings) {
    var output = {};
    for (int i = 0; i < inputStrings.length; i++) {
        var signature = getIsomorphicSignature(inputStrings[i]);
        if (!output[signature]) output[signature] = [];
        output[signature].push(inputStrings[i]);
    }
    return output;
}
user_4365600
Related