Algorithm 101 (Interview Question): 2 Ways to Determine if 2 Words are Isomorphic

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. - kennymkchan.

isomorphic("egg", "add"); //true
isomorphic("paper", "title"); // true
isomorphic("kick", "side"); // false
isomorphic("ACAB", "XCXY"); // false

Here, we assume that no character or letter can replace itself

Prerequisite

• Most Recurring Character
• Word Anagram
• Sentence Anagram

Let's Do this!

• Object, Array

function isomorphic(wordA, wordB) {
        // split the words
        let wordArrayA = [...wordA];
        let wordArrayB = [...wordB];
        let wordObject = {};

        // terminate if word length is not equal
        if (wordArrayA.length !== wordArrayB.length) {
          return "unequal word length";
        }

        // loop through to form an object
        for (let i = 0; i < wordArrayA.length; i++) {
          if (wordArrayA[i] != wordArrayB[1]) {
            if (wordObject.hasOwnProperty(wordArrayA[i])) {
              // create an array of keys and values
              let objectValues = Object.values(wordObject);
              let objectKeys = Object.keys(wordObject);

              // terminate if the already existing Key's value do not match the Key's value again
              if (
                objectValues[objectKeys.indexOf(wordArrayA[i])] !==
                wordArrayB[i]
              ) {
                return false;
              }
            } else {
              wordObject[wordArrayA[i]] = wordArrayB[i];
            }
          } else {
            return false;
          }
        }

        return true;
      }

• Object, string

function isomorphic(wordA, wordB) {
        let wordObject = {};

        // terminate if word length is not equal
        if (wordA.length !== wordA.length) {
          return "unequal word length";
        }

        // loop through to form an object
        for (let i = 0; i < wordA.length; i++) {
          if (wordA[i] !== wordB[i]) {
            // check if wordA already exist in the wordObject
            if (!wordObject[wordA[i]]) {
              wordObject[wordA[i]] = wordB[i];

              // terminate if the already existing Key's value do not match the Key's value again
            } else if (wordObject[wordA[i]] !== wordB[i]) {
              return false;
            }
          } else {
            return false;
          }
        }

        return true;
      }

Conclusion

Interview questions like this one we just solved tends to test how far you have dived into algorithm. As you must have noted, the solution to just this problem is built upon other algorithms we have solved in the past. So starting from the basics is very important.

There are many ways to solve problems programmatically. I will love to know other ways you solved yours in the comment section.

Up Next: Algorithm 202 (Interview Question): Matching Parenthesis in 2 Ways

If you have questions, comments or suggestions, please drop them in the comment section.

You can also follow and message me on social media platforms.

Twitter | LinkedIn | Github

Thank You For Your Time.

Comments

[Ganesh Shetty]

function isIsomorphic(str1, str2) {
var array = [];
var obj = {};
for (i = 0; i < str1.length; i++) {
if (!obj[str1[i]]) {
obj[str1[i]] = str2[i];
} else {
if (obj[str1[i]] !== str2[i]) {
console.log("NO ISOMORPHIC");
}
}
}
console.log(obj);
}
isIsomorphic("aab", "xyz");