205. Isomorphic Strings

    Isomorphic Strings

Problem Description

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

Two strings s and t 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

 

Constraints:

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ASCII character.

Idea:

Isomorphic means that if we exchange each character of the alphabet for some other (unique) character, it should present the new string. For example, the word add and egg are isomorphic. Character a is replaced by e and character d is replaced by g. Word ab and aa are not isomorphic. Character a is replaced by character a, and the next character b is also replaced by character a. They have to be unique.

The approach is as follows

• We declare two maps to keep the pairs for string map from string 1 to 2 and string 2 to 1
• We will loop over string one and check if all the pairs in map one map correctly to string two
• We will do the same with string 2
• If we find any mismatch anywhere, we return false as the string is not isomorphic
• If we reach the end of the program, it means strings were isomorphic. So we return to true

Let`s code it!

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) return false;

  const mapa = new Map();
  const mapb = new Map();

  for (let i = 0; i < s.length; i++) {
    if (mapa.has(s[i])) {
      if (mapa.get(s[i]) !== t[i]) {
        return false;
      }
    } else {
      mapa.set(s[i], t[i])
    }

    if (mapb.has(t[i])) {
      if (mapb.get(t[i]) !== s[i]) {
        return false;
      }
    } else {
      mapb.set(t[i], s[i])
    }
  }

  return true

};

Other Approaches)

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isIsomorphic = (s, t) => {
  const hashMap = new Map()
  const assignedValues = new Set()

  for (let i = 0; i < s.length; i++) {
    if (hashMap.has(s[i])) {
      if (hashMap.get(s[i]) !== t[i]) return false
    } else {
      if (assignedValues.has(t[i])) return false

      assignedValues.add(t[i])
      hashMap.set(s[i], t[i])
    }
  }

  return true
}

or

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isIsomorphic = (s, t) => {
  if (s.length !== t.length) {
    return false
  }

  const hashMap = new Map()

  for (let i = 0; i < s.length; i++) {
    if (!hashMap.has(s[i])) {
      hashMap.set(s[i], t[i])
    } else if (hashMap.get(s[i]) !== t[i]) {
      return false
    }
  }

  return new Set([...hashMap.values()]).size === hashMap.size
}

or

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isIsomorphic = (s, t) => {
  if (s.length !== t.length) {
    return false
  }

  const sHashMap = new Map()
  const tHashMap = new Map()

  for (let i = 0; i < s.length; i++) {
    if (
      (sHashMap.has(s[i]) && sHashMap.get(s[i]) !== t[i]) ||
      (tHashMap.has(t[i]) && tHashMap.get(t[i]) !== s[i])
    ) {
      return false
    }

    sHashMap.set(s[i], t[i])
    tHashMap.set(t[i], s[i])
  }

  return true
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #205. Isomorphic Strings

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!